Complete Binary Tree Inserter: BFS Queue Design
You are given the root of a complete binary tree. Design a data structure CBTInserter that supports three operations: initialize with the given tree, insert a new node while maintaining the complete binary tree property, and return the root. The insert method should return the value of the new node's parent.
This is LeetCode 919: Complete Binary Tree Inserter. The key constraint is that the tree must remain complete after every insertion. A complete binary tree fills each level left to right, so the next insertion always goes to the leftmost available position on the deepest level. The question is: how do you find that position in O(1) time?
The core idea: maintain a deque of incomplete nodes
A complete binary tree fills nodes left to right. So the next insertion target is always the first node (in BFS order) that does not yet have two children. If you maintain a deque of all such nodes, the front of the deque is always the parent for the next insertion.
Here is the approach:
- Constructor: run BFS on the initial tree. For each node, if it is missing a left or right child, append it to the deque. This captures all nodes that can still accept children, in BFS order.
insert(val): look at the front of the deque. That node is the parent. If the parent has no left child, attach the new node as its left child. Otherwise, attach it as the right child and pop the parent from the deque (since it now has two children). Either way, push the new node to the back of the deque (it is a leaf that can accept future children). Return the parent's value.get_root(): return the root stored during initialization.
The deque always stays in BFS order. Nodes at the front are closer to the root, nodes at the back are the most recently added leaves. This means the front always points to the correct insertion target for maintaining completeness.
Python solution
from collections import deque
class CBTInserter:
def __init__(self, root):
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):
node = TreeNode(val)
parent = self.deque[0]
if not parent.left:
parent.left = node
else:
parent.right = node
self.deque.popleft()
self.deque.append(node)
return parent.val
def get_root(self):
return self.root
The constructor does one BFS pass to find all incomplete nodes. After that, every insert call is O(1) because you just peek at the front of the deque, attach the new node, and possibly pop.
Notice that the BFS in the constructor adds a node to the deque if it is missing either child. This correctly handles the case where the front node already has a left child but not a right child (like node 3 in the example tree).
Walkthrough: inserting into tree [1, 2, 3, 4, 5, 6]
Starting with the tree [1, 2, 3, 4, 5, 6], the BFS initialization builds the deque [3, 4, 5, 6]. Node 3 is at the front because it is the first node (in BFS order) missing a child. It has a left child (6) but no right child.
insert(7): Parent is node 3 (front of deque). Attach as right child.
Node 3 now has two children, so pop it from the front. Push node 7 to the back of the deque. Deque becomes [4, 5, 6, 7]. Return 3.
insert(8): Parent is node 4 (front of deque). Attach as left child.
Node 4 still needs a right child, so it stays at the front. Push node 8 to the back. Deque becomes [4, 5, 6, 7, 8]. Return 4.
After both insertions, the tree is [1, 2, 3, 4, 5, 6, 7, 8]. The deque correctly tracks which nodes can still accept children, and each insert took O(1) time.
Complexity analysis
| Operation | Time | Space |
|---|---|---|
| Constructor | O(n) | O(n) |
insert(val) | O(1) | O(1) |
get_root() | O(1) | O(1) |
| Overall space | O(n) |
The constructor performs a full BFS, visiting all n nodes once. The deque holds at most n/2 + 1 nodes (all leaf nodes plus possibly one internal node), which is O(n). Each insert call does a constant number of deque operations: peek, possibly popleft, and append.
Edge cases
- Single node tree: the root has no children, so the deque starts as
[root]. The first insert attaches as left child. The root stays at the front since it still needs a right child. - Perfect tree (all levels full): every node has two children, so the deque contains only the leaves. The first insert attaches as the left child of the leftmost leaf, starting a new level.
- Tree with only left child at the bottom-right: this is the standard "almost complete" case. The deque front is the node missing its right child. After filling it, the front advances to the next leaf.
The building blocks
This problem is built on two reusable building blocks:
1. BFS level-order traversal. The constructor uses BFS to visit nodes in the exact order they would be filled. This is the same traversal you use for level order traversal, serialization, and any problem where you need to process nodes top to bottom, left to right. The key insight is that BFS order in a complete binary tree matches the array index order.
2. Amortized O(1) queue operations. The deque here is not just a data structure, it is an invariant. By maintaining a queue of "available" nodes in BFS order, you turn what could be an O(n) search for the next insertion point into an O(1) peek. This same pattern of pre-computing a queue of candidates shows up in problems like Populating Next Right Pointers and Connect Nodes at Same Level.
Both blocks combine to give you a design that answers "where does the next node go?" without re-traversing the tree on every insert.
From understanding to recall
You now see how CBTInserter works: BFS to find incomplete nodes, deque to track insertion order, peek at the front for the parent. The constructor is the only expensive operation. Everything after that is constant time.
In an interview, you need to recall three things: the BFS initialization that filters for incomplete nodes, the insert logic that checks left vs. right and conditionally pops, and the fact that every new node gets appended to the deque. These are small details, but missing any one of them breaks the solution.
Spaced repetition turns understanding into automatic recall. You write the CBTInserter class from scratch after one day, then three days, then a week. Each time, you reconstruct the BFS initialization, the deque invariant, and the insert/pop logic from memory. After a few rounds, you stop thinking about which condition triggers a popleft and just write it.
The two building blocks (BFS traversal and amortized queue maintenance) transfer directly to other design problems that require maintaining tree structure across multiple operations.
Related posts
- Binary Tree Level Order Traversal - The BFS traversal pattern that forms the foundation of this approach
- Implement Queue Using Stacks - Another design problem involving queue-based data structure operations
- Binary Search Tree Iterator - A similar iterator-style design problem for tree structures