Code Implementation

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class CBTInserter:

    def __init__(self, root: TreeNode):
        self.root = root
        self.deque = deque()
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if not node.left or not node.right:
                self.deque.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def insert(self, val: int) -> int:
        node = self.deque[0]
        new_node = TreeNode(val)
        if not node.left:
            node.left = new_node
        else:
            node.right = new_node
            self.deque.popleft()
        self.deque.append(new_node)
        return node.val

    def get_root(self) -> TreeNode:
        return self.root
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <queue>
using namespace std;

class CBTInserter {
private:
    TreeNode* root;
    queue<TreeNode*> q;
public:
    CBTInserter(TreeNode* root) {
        this->root = root;
        queue<TreeNode*> tmp;
        tmp.push(root);
        while (!tmp.empty()) {
            TreeNode* node = tmp.front(); tmp.pop();
            if (!node->left || !node->right)
                q.push(node);
            if (node->left) tmp.push(node->left);
            if (node->right) tmp.push(node->right);
        }
    }
    
    int insert(int v) {
        TreeNode* node = q.front();
        TreeNode* newNode = new TreeNode(v);
        if (!node->left) {
            node->left = newNode;
        } else {
            node->right = newNode;
            q.pop();
        }
        q.push(newNode);
        return node->val;
    }
    
    TreeNode* get_root() {
        return root;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

class CBTInserter {
    private TreeNode root;
    private Queue<TreeNode> queue;

    public CBTInserter(TreeNode root) {
        this.root = root;
        queue = new LinkedList<>();
        Queue<TreeNode> temp = new LinkedList<>();
        temp.offer(root);
        while (!temp.isEmpty()) {
            TreeNode node = temp.poll();
            if (node.left == null || node.right == null) {
                queue.offer(node);
            }
            if (node.left != null) temp.offer(node.left);
            if (node.right != null) temp.offer(node.right);
        }
    }
    
    public int insert(int v) {
        TreeNode node = queue.peek();
        TreeNode newNode = new TreeNode(v);
        if (node.left == null) {
            node.left = newNode;
        } else {
            node.right = newNode;
            queue.poll();
        }
        queue.offer(newNode);
        return node.val;
    }
    
    public TreeNode get_root() {
        return root;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var CBTInserter = function(root) {
    this.root = root;
    this.queue = [];
    let q = [root];
    while (q.length) {
        let node = q.shift();
        if (!node.left || !node.right) {
            this.queue.push(node);
        }
        if (node.left) q.push(node.left);
        if (node.right) q.push(node.right);
    }
};

CBTInserter.prototype.insert = function(val) {
    let node = this.queue[0];
    let newNode = new TreeNode(val);
    if (!node.left) {
        node.left = newNode;
    } else {
        node.right = newNode;
        this.queue.shift();
    }
    this.queue.push(newNode);
    return node.val;
};

CBTInserter.prototype.get_root = function() {
    return this.root;
};
      

Problem Description

You are given the root of a complete binary tree, and you need to design a data structure called CBTInserter that supports two operations:

• insert(val): Inserts a new node with value val into the tree so that the tree remains a complete binary tree. The method returns the value of the parent node to which the new node was attached.
• get_root(): Returns the root node of the tree.

The key constraints are:

• The tree is always a complete binary tree: all levels are fully filled except possibly the last, which is filled from left to right.
• Each insertion must keep the tree complete.
• There is exactly one valid way to insert a node at each step.
• No elements are reused or overwritten.

Thought Process

The challenge is to efficiently insert nodes into a complete binary tree while maintaining its completeness property. A brute-force approach would be to traverse the tree for every insertion to find the first available spot, but this would be inefficient, especially as the tree grows.

Instead, we should look for a way to quickly identify where the next insertion should occur. In a complete binary tree, nodes are filled from left to right at each level. This means that the first node missing a child (either left or right) is always the correct insertion point. By tracking these "incomplete" nodes, we can insert new nodes in constant time.

The key insight is to use a queue to store nodes that do not yet have two children. This way, we always know where to insert the next node without traversing the entire tree.

Solution Approach

To implement the CBTInserter, we use the following steps:

1. Initialization:
   • Perform a level-order (breadth-first) traversal of the tree starting from the root.
   • For each node, if it has less than two children, add it to a queue (let's call it deque).
   • This queue will always contain nodes that are available for insertion.
2. Insertion:
   • The node at the front of the deque is the next available insertion point.
   • If its left child is missing, insert the new node as the left child.
   • If its left child exists but the right child is missing, insert the new node as the right child and remove this node from the deque (since it now has two children).
   • Add the newly inserted node to the deque (it may need children in the future).
   • Return the value of the parent node.
3. Get Root:
   • Simply return the stored root node.

This approach ensures that every insertion is performed in constant time, and the tree remains complete after each operation.

Example Walkthrough

Suppose the starting tree is:

        1
       / \
      2   3
     /
    4
  

Step 1: Initialization

• Level order traversal finds nodes with missing children: 2 (missing right), 3 (missing left), 4 (missing left and right).
• Queue after initialization: [2, 3, 4]

• Front of queue is node 2.
• Node 2's right child is missing, so insert 5 as its right child.
• Node 2 now has two children, so remove it from the queue.
• Add new node 5 to queue: [3, 4, 5]
• Return 2 (parent value).

• Front of queue is node 3.
• Node 3's left child is missing, so insert 6 as its left child.
• Node 3 still needs a right child, so keep in queue.
• Add new node 6 to queue: [3, 4, 5, 6]
• Return 3 (parent value).

• Front of queue is node 3.
• Node 3's right child is missing, so insert 7 as its right child.
• Node 3 now has two children, so remove from queue.
• Add new node 7 to queue: [4, 5, 6, 7]
• Return 3.

At each step, the tree remains a complete binary tree and insertions are efficient.

Time and Space Complexity

Brute-force Approach:

• For each insertion, traverse the tree to find the first available spot, which takes O(N) time per insertion (N = number of nodes).
• Space: O(N) for the tree structure.

• Initialization: O(N) time and space for the level-order traversal and building the queue.
• Each insert: O(1) time, since we always access the front of the queue.
• Space: O(N), since the queue may contain up to N nodes in the worst case (when the last level is only half-filled).

The optimized approach is much more efficient for repeated insertions.

Summary

The CBTInserter efficiently maintains a complete binary tree by tracking nodes that are available for insertion using a queue. This allows each insertion to occur in constant time, always preserving the complete tree property. The key insight is to use level-order traversal for initialization and a queue to avoid unnecessary traversals for each insertion, making the solution both elegant and efficient.