Complete Binary Tree Inserter

Problem Statement

In the context of binary trees, a complete binary tree is defined as one in which every level—except possibly the last—is completely filled, and all nodes are as far left as possible.

Your task is to design a class CBTInserter that:

• Initializes with the root of an existing complete binary tree.
• Allows inserting new nodes while maintaining the completeness property.
• Provides access to the current root node.

The operations to implement include:

1. CBTInserter(TreeNode root) – Initializes the data structure with the given root.
2. int insert(int val) – Inserts a new node with value val in a way that maintains tree completeness. Returns the value of the parent node to which the new node was added.
3. TreeNode get_root() – Returns the root node of the tree after all insertions.

Examples

Example 1

Input:

["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]

Output:

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

Explanation:

1. CBTInserter cBTInserter = new CBTInserter([1, 2]);
   Initializes the tree with root 1 and left child 2.

2. cBTInserter.insert(3); ➜ returns 1
   Adds 3 as the right child of node 1.

3. cBTInserter.insert(4); ➜ returns 2
   Adds 4 as the left child of node 2.

4. cBTInserter.get_root(); ➜ returns [1, 2, 3, 4]
   Returns the updated tree in level order.

Constraints

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

Approach and Intuition

Maintaining completeness during insertions requires identifying the next available position in level order (left to right, top to bottom). A queue makes this efficient.

Key Ideas

1. Track Incomplete Nodes:

   • Use a queue to store nodes that are missing at least one child.
   • Always insert new nodes as children of the node at the front of the queue.

2. Insert Operation:

   • Peek the front node of the queue.
   • If it has no left child, insert there.
   • Otherwise, insert at the right.
   • If the node now has both children, remove it from the queue.
   • Enqueue the newly added node (it may receive children later).
   • Return the value of the parent node.

3. Get Root Operation:

   • Return the root node stored during initialization.

Why This Works

• This approach guarantees O(1) access to the next insertion point using the queue.
• It ensures each level is filled from left to right.
• Space complexity is O(n) for storing the tree and queue references.

Example Detailed Walkthrough

• Initial tree: [1, 2]. Node 1 has left child 2.
• Insert 3: Node 1 gets 3 as right child. Now both its children are filled, so it's removed from the queue.
• Insert 4: Node 2 gets 4 as left child.
• Final tree structure (level order): [1, 2, 3, 4].

This method leverages BFS and a queue to ensure that insertions always respect the structure of a complete binary tree.

Solutions

class CompleteBinaryTreeInserter {
    TreeNode rootNode;
    Deque<TreeNode> nodeDeque;
    
    public CompleteBinaryTreeInserter(TreeNode rootNode) {
        this.rootNode = rootNode;
        nodeDeque = new ArrayDeque<>();
        Queue<TreeNode> bfsQueue = new ArrayDeque<>();
        bfsQueue.offer(rootNode);

        while (!bfsQueue.isEmpty()) {
            TreeNode currentNode = bfsQueue.poll();
            if (currentNode.left == null || currentNode.right == null)
                nodeDeque.offerLast(currentNode);
            if (currentNode.left != null)
                bfsQueue.offer(currentNode.left);
            if (currentNode.right != null)
                bfsQueue.offer(currentNode.right);
        }
    }

    public int insert(int value) {
        TreeNode newNode = new TreeNode(value);
        TreeNode parentNode = nodeDeque.peekFirst();
        nodeDeque.offerLast(newNode);
        
        if (parentNode.left == null)
            parentNode.left = newNode;
        else {
            parentNode.right = newNode;
            nodeDeque.pollFirst();
        }

        return parentNode.val;
    }

    public TreeNode getRoot() {
        return rootNode;
    }
}