Complete Binary Tree Inserter - Video Solutions
Complete Binary Tree Inserter
Complete Binary Tree Inserter - Video Solution
Watch 10 video solutions for Complete Binary Tree Inserter, a medium level problem involving Tree, Breadth-First Search, Design. This walkthrough by Pepcoding has 3,111 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 therootof the complete binary tree.int insert(int v)Inserts aTreeNodeinto the tree with valueNode.val == valso that the tree remains complete, and returns the value of the parent of the insertedTreeNode.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:
- The number of nodes in the tree will be in the range
[1, 1000]. 0 <= Node.val <= 5000rootis a complete binary tree.0 <= val <= 5000- At most
104calls will be made toinsertandget_root.
Approach Overview
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.
Complexity Analysis
| 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 |