LeetCode-in-Java

919. Complete Binary Tree Inserter

Medium

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.

Implement the CBTInserter class:

• CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree.
• int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode.
• TreeNode get_root() Returns the root node of the tree.

Example 1:

Input [“CBTInserter”, “insert”, “insert”, “get_root”] [[[1, 2]], [3], [4], []]

Output: [null, 1, 2, [1, 2, 3, 4]]

Explanation:

CBTInserter cBTInserter = new CBTInserter([1, 2]); 
cBTInserter.insert(3); // return 1 
cBTInserter.insert(4); // return 2 
cBTInserter.get\_root(); // return [1, 2, 3, 4]

Constraints:

• The number of nodes in the tree will be in the range [1, 1000].
• 0 <= Node.val <= 5000
• root is a complete binary tree.
• 0 <= val <= 5000
• At most 104 calls will be made to insert and get_root.

Solution

import com_github_leetcode.TreeNode;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/*
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class CBTInserter {
    private final Queue<TreeNode> q;
    private final TreeNode head;

    public CBTInserter(TreeNode root) {
        this.q = new LinkedList<>();
        this.head = root;
        addToQueue();
    }

    private void addToQueue() {
        Queue<TreeNode> hlq = new LinkedList<>();
        hlq.add(this.head);
        while (!hlq.isEmpty()) {
            int size = hlq.size();
            while (size-- > 0) {
                TreeNode poll = hlq.poll();
                this.q.add(poll);
                if (Objects.requireNonNull(poll).left != null) {
                    hlq.add(poll.left);
                }
                if (poll.right != null) {
                    hlq.add(poll.right);
                }
            }
        }
    }

    public int insert(int val) {
        TreeNode nn = new TreeNode(val);
        deleteFullNode();
        TreeNode peek = q.peek();
        if (Objects.requireNonNull(peek).left == null) {
            peek.left = nn;
        } else {
            peek.right = nn;
        }
        this.q.add(nn);
        return peek.val;
    }

    private void deleteFullNode() {
        while (!this.q.isEmpty()) {
            TreeNode peek = this.q.peek();
            if (peek.left != null && peek.right != null) {
                this.q.poll();
            } else {
                break;
            }
        }
    }

    // get_root()
    public TreeNode getRoot() {
        return this.head;
    }
}

/*
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(val);
 * TreeNode param_2 = obj.get_root();
 */

This site is open source. Improve this page.