Complete Binary Tree Inserter

medium binary tree queue design

Problem

A complete binary tree is a tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Design a CBTInserter initialized with the root of a complete binary tree that supports insert(v): append a new node with value v so the tree stays complete and return the value of the new node's parent. get_root() returns the root.

Inputinit = [1, 2], insert(3), insert(4)

Output1, 2

Insert 3 as the right child of 1 (parent value 1). Insert 4 as the left child of 2 (parent value 2).

initial values (level order, comma-separated)

values to insert (comma-separated)

from collections import deque

class CBTInserter:
    def __init__(self, root):
        self.root = root
        self.q = deque()
        bfs = deque([root])
        while bfs:
            node = bfs.popleft()
            if node.left: bfs.append(node.left)
            if node.right: bfs.append(node.right)
            if not node.left or not node.right:
                self.q.append(node)

    def insert(self, v):
        node = TreeNode(v)
        parent = self.q[0]
        if not parent.left:
            parent.left = node
        else:
            parent.right = node
            self.q.popleft()
        self.q.append(node)
        return parent.val

    def get_root(self):
        return self.root

class CBTInserter {
  constructor(root) {
    this.root = root;
    this.q = [];
    const bfs = [root];
    while (bfs.length) {
      const node = bfs.shift();
      if (node.left) bfs.push(node.left);
      if (node.right) bfs.push(node.right);
      if (!node.left || !node.right) this.q.push(node);
    }
  }
  insert(v) {
    const node = new TreeNode(v);
    const parent = this.q[0];
    if (!parent.left) {
      parent.left = node;
    } else {
      parent.right = node;
      this.q.shift();
    }
    this.q.push(node);
    return parent.val;
  }
  get_root() {
    return this.root;
  }
}

class CBTInserter {
    TreeNode root;
    Queue<TreeNode> q = new LinkedList<>();
    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> bfs = new LinkedList<>();
        bfs.add(root);
        while (!bfs.isEmpty()) {
            TreeNode node = bfs.poll();
            if (node.left != null) bfs.add(node.left);
            if (node.right != null) bfs.add(node.right);
            if (node.left == null || node.right == null) q.add(node);
        }
    }
    public int insert(int v) {
        TreeNode node = new TreeNode(v);
        TreeNode parent = q.peek();
        if (parent.left == null) {
            parent.left = node;
        } else {
            parent.right = node;
            q.poll();
        }
        q.add(node);
        return parent.val;
    }
    public TreeNode get_root() { return root; }
}

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

Explanation

A complete binary tree fills in left-to-right, level by level, so the next node always attaches to the shallowest node that still has a free child slot. The key insight is to keep a queue of exactly those "not-yet-full" nodes, so every insert is O(1).

In the constructor we do a BFS over the existing tree and push into self.q every node that is missing a left or right child. The front of the queue is therefore always the node that should receive the next inserted child.

For insert(v), we peek the front parent = self.q[0]. If its left slot is empty we attach there; otherwise we attach to the right and, since that node is now full, we popleft() it off the queue. The brand-new node always has two empty slots, so we append it to the back with self.q.append(node), and we return parent.val.

Example: starting from [1, 2], the queue holds node 1 (missing a right child) and node 2. insert(3) sees node 1 already has a left child (2), so 3 becomes its right child, node 1 is popped, and we return 1. insert(4) sees node 2 has an empty left slot, attaches 4 there, and returns 2.

Time: O(1) per insert, O(n) init Space: O(n)