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.Problem Overview: Design a class that inserts nodes into a complete binary tree while preserving the complete-tree property. Each insertion must place the new node in the leftmost available position of the last level and return the parent node's value.
Approach 1: Breadth-First Search using a Queue (Initialization O(n), Insert O(1) time, O(n) space)
The key observation: in a complete binary tree, insertion always happens at the first node that is missing a child. During initialization, run a breadth-first search and push every node with fewer than two children into a queue. The front of the queue always represents the next valid parent for insertion. When inserting, attach the new node as the left child if missing, otherwise as the right child and remove the parent from the queue because it is now full. Add the new node to the queue since it may accept future children. Initialization costs O(n) time, but each insert() runs in O(1) time with O(n) space for the queue.
Approach 2: Level Order Traversal for Insertion (O(n) time per insert, O(n) space)
This method performs a fresh level-order traversal every time you insert a node. Starting from the root, use a queue to scan nodes level by level until you find the first node that does not have two children. Insert the new node as the left child if it is empty; otherwise attach it to the right. The traversal guarantees the complete-tree property because nodes are explored strictly from left to right across each level. The downside is repeated work: each insertion may scan the entire binary tree, leading to O(n) time per operation and O(n) auxiliary queue space.
Recommended for interviews: The queue-based BFS design is the expected solution. It preprocesses the tree once and keeps a list of candidate parents, turning insertion into a constant-time operation. Interviewers like this approach because it demonstrates understanding of tree structure invariants and efficient state maintenance. The level-order traversal method is easier to reason about initially and shows understanding of the complete-tree property, but the optimized queue design proves stronger algorithmic thinking.
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.
We 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).
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.
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.
In this Java solution, for every insert call, we perform a level order traversal from the root node to find where the new value should go. A standard queue supports the traversal to ensure the completeness property of the binary tree.
The get_root operation directly returns the stored root. This approach can be less optimal than using a persistent queue but systematically searches for the next possible insertion point.
Java
JavaScript
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.
We can use an array tree to store all nodes of the complete binary tree. During initialization, we use a queue q to perform level-order traversal of the given tree and store all nodes into the array tree.
When inserting a node, we can find the parent node p of the new node through the array tree. Then we create a new node node, insert it into the array tree, and make node as the left child or right child of p. Finally, we return the value of p.
When getting the root node, we directly return the first element of the array tree.
In terms of time complexity, it takes O(n) time for initialization, and the time complexity for inserting a node and getting the root node are both O(1). The space complexity is O(n), where n is the number of nodes in the tree.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search using a Queue | 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. |
| Approach 2: Level Order Traversal for Insertion | 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. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search Queue (Candidate Parents) | Init: O(n), Insert: O(1) | O(n) | Best choice for repeated insert operations and interview solutions |
| Level Order Traversal Per Insert | O(n) per insert | O(n) | Simple approach when insert operations are rare or for conceptual understanding |
Complete Binary Tree Inserter • Pepcoding • 3,092 views views
Watch 6 more video solutions →Practice Complete Binary Tree Inserter with our built-in code editor and test cases.
Practice on FleetCode