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:
[1, 1000].0 <= Node.val <= 5000root is a complete binary tree.0 <= val <= 5000104 calls will be made to insert and get_root.The key idea behind #919 Complete Binary Tree Inserter is maintaining the complete binary tree property while supporting efficient insert operations. A common strategy is to use Breadth-First Search (BFS) to track nodes that do not yet have two children.
During initialization, perform a BFS traversal of the tree and store candidate nodes (those with at least one missing child) in a queue. When inserting a new value, attach it to the first node in the queue—either as the left child if available, otherwise as the right child. Once a node has both children, it is removed from the queue. The newly inserted node is then added to the queue as a potential parent for future insertions.
This design ensures that each insertion preserves the complete tree structure while keeping operations efficient. The initialization step takes O(n) time, while each insert operation runs in O(1) time with O(n) space used to maintain the queue.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS with candidate queue | Initialization: O(n), Insert: O(1) | O(n) |
NeetCode
The idea is to use a queue to track the nodes at the current level and help find where to insert a new node to maintain the complete binary tree property.
When inserting, always maintain a queue that holds nodes which can potentially have children added to them. Initially, populate the queue with nodes from the complete tree using level-order traversal where a node is added only if it can further accommodate more children.
For each insertion, take the node from the front of the queue and insert the new child. If a node has both children filled after insertion, remove it from the queue. New nodes always get added to the end of the queue to maintain the complete binary tree property.
Both the insertion and retrieving the root operations run with O(1) time complexity. The space complexity is O(n) for storing nodes in the deque.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class CBTInserter:
10 def __init__(self, root: TreeNode):
11 self.root = root
12 self.deque = deque()
13 queue = deque([root])
14 while queue:
15 node = queue.popleft()
16 if not node.left or not node.right:
17 self.deque.append(node)
18 if node.left:
19 queue.append(node.left)
20 if node.right:
21 queue.append(node.right)
22
23 def insert(self, v: int) -> int:
24 parent = self.deque[0]
25 new_node = TreeNode(v)
26 if not parent.left:
27 parent.left = new_node
28 else:
29 parent.right = new_node
30 self.deque.popleft()
31 self.deque.append(new_node)
32 return parent.val
33
34 def get_root(self) -> TreeNode:
35 return self.rootWe initialize the class by performing a level-order traversal of the tree to add each node to a queue if it can have children nodes added.
During insertion, we check the first node in our queue for having a room for a new child (left or right). We insert the new node, if both children nodes are filled, then we remove the parent from the queue as it's full and add the newly inserted node to maintain order.
Time complexity for initializing the class constructor is O(n) and for insert operation is O(1).
This approach still employs a level order traversal starting from the root for every insertion to find the first available spot, thus maintaining the complete binary tree properties.
With each insertion, traverse the tree using a queue to ensure for each node, you check if it is either missing a left or right child. Stop and insert the new node at the first possible position found.
Even though this method is less efficient during each insert because of repeated traversal, it effectively maintains tree completeness by directly probing the current state of the tree.
For the `insert` method, the time complexity per insertion operation can reach O(n) in the worst case if re-traversing the tree is required. The `get_root` call is O(1).
Space complexity is O(n) for managing the additional queue during the insertion process.
1class TreeNode {
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
BFS naturally processes nodes level by level, which matches how complete binary trees are filled. This ensures new nodes are added from left to right at the lowest possible level.
Yes, variations of this problem appear in technical interviews at large tech companies. It tests understanding of binary tree properties, BFS traversal, and designing efficient data structures.
A queue (often implemented as a deque) is ideal for this problem. It stores nodes that are eligible to receive new children, allowing efficient insertion while maintaining level-order structure.
The optimal approach uses a BFS-based queue to track nodes that are missing children. By always inserting under the earliest available node, the complete tree property is preserved and each insert operation can run in constant time.
The JavaScript solution mirrors the Java approach in creating and managing a queue for each insertion. We explore the tree from the root, seeking an open child position to insert the new node.
Insertions systematically search throughout the tree due to the level-order traversal accompanying it, with a focus on preserving the complete nature of the binary tree.