Complete Binary Tree Inserter

Med

#0873Time: `CBTInserter`: O(1) `insert`: O(N), where N is the number of nodes in the tree. In the worst case, we traverse all N nodes to find the insertion point. `get_root`: O(1)Space: O(W), where W is the maximum width of the tree. For a complete binary tree, W can be up to (N+1)/2, making the space complexity O(N). This space is used by the queue during the BFS traversal in the `insert` method.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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:

The number of nodes in the tree will be in the range [1, 1000].
0 <= Node.val <= 5000
root is a complete binary tree.
0 <= val <= 5000
At most 10⁴ calls will be made to insert and get_root.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves finding the correct insertion point for each new node by traversing the tree from the root every time insert is called. A complete binary tree requires the new node to be placed at the first available position from the left in the lowest level. This position can be found using a Breadth-First Search (BFS), also known as a level-order traversal.

Algorithm

CBTInserter(root):
- Store the root node in a member variable.
insert(val):
1. Initialize a queue for Breadth-First Search (BFS) and add the root to it.
2. Start a loop that continues as long as the queue is not empty.
3. In each iteration, dequeue a node, let's call it current.
4. Check if current.left is null. If it is, this is the first available spot. Create a new TreeNode with val, set it as current.left, and return current.val.
5. If current.left is not null, add it to the queue to visit its children later.
6. Check if current.right is null. If it is, this is the next available spot. Create the new node, set it as current.right, and return current.val.
7. If current.right is not null, add it to the queue.
get_root():
- Return the stored root node.

Walkthrough

The constructor, CBTInserter(root), simply stores a reference to the root of the tree, which is an O(1) operation. The main logic resides in the insert(val) method. For each call to insert, we perform a full level-order traversal starting from the root. We use a queue to manage the nodes to visit. We explore the tree level by level, from left to right. The first time we encounter a node that has a null left child, we place the new node there. If the left child is already present, we check the right child. If the right child is null, we insert the new node there. If both children are present, we add both children to the queue and continue the search. This process guarantees that we find the first available spot as required for a complete binary tree, but it requires re-scanning a significant portion of the tree for every single insertion.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class CBTInserter {17    private TreeNode root;18 19    public CBTInserter(TreeNode root) {20        this.root = root;21    }22 23    public int insert(int val) {24        Queue<TreeNode> queue = new LinkedList<>();25        queue.offer(this.root);26 27        while (!queue.isEmpty()) {28            TreeNode node = queue.poll();29 30            if (node.left == null) {31                node.left = new TreeNode(val);32                return node.val;33            } else {34                queue.offer(node.left);35            }36 37            if (node.right == null) {38                node.right = new TreeNode(val);39                return node.val;40            } else {41                queue.offer(node.right);42            }43        }44        return -1; // Should not be reached given the problem constraints45    }46 47    public TreeNode get_root() {48        return this.root;49    }50}

Complexity

Time

`CBTInserter`: O(1) `insert`: O(N), where N is the number of nodes in the tree. In the worst case, we traverse all N nodes to find the insertion point. `get_root`: O(1)

Space

O(W), where W is the maximum width of the tree. For a complete binary tree, W can be up to (N+1)/2, making the space complexity O(N). This space is used by the queue during the BFS traversal in the `insert` method.

Trade-offs

Pros

Simple to understand and implement.
It does not require any extra persistent data structures besides the tree itself.

Cons

The insert operation is inefficient with a time complexity of O(N).
For a large number of insert calls, this approach can be very slow as it repeatedly traverses a growing tree from the root.

To avoid re-traversing the tree on every insertion, we can pre-process the tree and maintain a data structure that gives us direct access to the nodes that are available to be parents. In a complete binary tree, new nodes are added to the left-most available spot. The parents of these new nodes will be the first nodes in a level-order traversal that are not "full" (i.e., have fewer than two children). We can use a queue to store these potential parent nodes, allowing for O(1) insertions.

Algorithm

CBTInserter(root):
1. Initialize a queue, candidates, to store nodes that can accept new children.
2. Store the root in a member variable.
3. Perform a one-time level-order traversal (BFS) of the initial tree.
4. During the traversal, for each node visited, if it has fewer than two children (node.left == null or node.right == null), add it to the candidates queue.
insert(val):
1. Get the parent for the new node by peeking at the front of the candidates queue (parent = candidates.peek()).
2. Create the new node, newNode, with the given value val.
3. Add newNode to the back of the candidates queue, as it's a potential parent for future insertions.
4. If parent.left is null, attach newNode as the left child.
5. Otherwise, parent.right must be null. Attach newNode as the right child. Since this makes the parent node full, remove it from the front of the candidates queue.
6. Return parent.val.
get_root():
- Return the stored root node.

Walkthrough

This optimized approach trades a one-time setup cost for highly efficient insertions.

In the constructor CBTInserter(root), we perform a single BFS traversal over the entire initial tree. The purpose of this traversal is to find all nodes that are not yet full (i.e., have at least one null child pointer). We add these nodes to a dedicated queue, which we'll call candidates. Because we find them via BFS, they are naturally ordered by level, from left to right. The node at the front of this candidates queue is precisely the parent where the next insertion must occur.

When insert(val) is called, we don't need to search the tree. We simply peek() at the candidates queue to get the parent node. We create the new node and attach it to the parent's first available child slot (left, then right). The new node itself is now a candidate for being a parent, so we add it to the candidates queue. If attaching the new node made the parent node full (i.e., we filled its right child slot), we poll() the parent from the candidates queue. This entire process involves a few simple queue operations, making it O(1).

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class CBTInserter {17    private TreeNode root;18    private Queue<TreeNode> candidates;19 20    public CBTInserter(TreeNode root) {21        this.root = root;22        this.candidates = new LinkedList<>();23        Queue<TreeNode> q = new LinkedList<>();24        q.offer(root);25 26        while (!q.isEmpty()) {27            TreeNode node = q.poll();28            if (node.left == null || node.right == null) {29                this.candidates.offer(node);30            }31            if (node.left != null) {32                q.offer(node.left);33            }34            if (node.right != null) {35                q.offer(node.right);36            }37        }38    }39 40    public int insert(int val) {41        TreeNode parent = this.candidates.peek();42        TreeNode newNode = new TreeNode(val);43        this.candidates.offer(newNode);44 45        if (parent.left == null) {46            parent.left = newNode;47        } else { // parent.right must be null48            parent.right = newNode;49            this.candidates.poll(); // This parent is now full, remove it50        }51        return parent.val;52    }53 54    public TreeNode get_root() {55        return this.root;56    }57}

Complexity

Time

`CBTInserter`: O(N), for the initial BFS to populate the `candidates` queue. `insert`: O(1). All queue operations (peek, offer, poll) are constant time. `get_root`: O(1).

Space

O(W), where W is the maximum width of the tree. The `candidates` queue stores non-full nodes, which are located in the last and second-to-last levels. The number of nodes in these levels is at most `(N+1)/2 + (N+1)/4`, so the space complexity is O(N).

Trade-offs

Pros

Extremely efficient insert operation with O(1) time complexity.
The one-time setup cost in the constructor is amortized over all subsequent insert calls, making it ideal for scenarios with many insertions.

Cons

Requires additional space for the queue of candidate parent nodes.
The constructor has a one-time setup cost of O(N) in both time and space.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class CBTInserter { private List < TreeNode > tree ; public CBTInserter ( TreeNode root ) { tree = new ArrayList <>(); Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { TreeNode node = q . pollFirst (); tree . add ( node ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } public int insert ( int val ) { int pid = ( tree . size () - 1 ) >> 1 ; TreeNode node = new TreeNode ( val ); tree . add ( node ); TreeNode p = tree . get ( pid ); if ( p . left == null ) { p . left = node ; } else { p . right = node ; } return p . val ; } public TreeNode get_root () { return tree . get ( 0 ); } } /** * Your CBTInserter object will be instantiated and called as such: * CBTInserter obj = new CBTInserter(root); * int param_1 = obj.insert(val); * TreeNode param_2 = obj.get_root(); */

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root */ var CBTInserter = function ( root ) { this . tree = []; const q = [ root ]; while ( q . length ) { const node = q . shift (); this . tree . push ( node ); if ( node . left ) { q . push ( node . left ); } if ( node . right ) { q . push ( node . right ); } } }; /** * @param {number} val * @return {number} */ CBTInserter . prototype . insert = function ( val ) { const pid = ( this . tree . length - 1 ) >> 1 ; const node = new TreeNode ( val ); this . tree . push ( node ); const p = this . tree [ pid ]; if ( ! p . left ) { p . left = node ; } else { p . right = node ; } return p . val ; }; /** * @return {TreeNode} */ CBTInserter . prototype . get_root = function () { return this . tree [ 0 ]; }; /** * Your CBTInserter object will be instantiated and called as such: * var obj = new CBTInserter(root) * var param_1 = obj.insert(val) * var param_2 = obj.get_root() */

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class CBTInserter { public: vector < TreeNode *> tree ; CBTInserter ( TreeNode * root ) { queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { auto node = q . front (); q . pop (); tree . push_back ( node ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } } int insert ( int val ) { int pid = tree . size () - 1 >> 1 ; TreeNode * node = new TreeNode ( val ); tree . push_back ( node ); TreeNode * p = tree [ pid ]; if ( ! p -> left ) p -> left = node ; else p -> right = node ; return p -> val ; } TreeNode * get_root () { return tree [ 0 ]; } }; /** * Your CBTInserter object will be instantiated and called as such: * CBTInserter* obj = new CBTInserter(root); * int param_1 = obj->insert(val); * TreeNode* param_2 = obj->get_root(); */

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class CBTInserter : def __init__ ( self , root : TreeNode ): self . tree = [] q = deque ([ root ]) while q : for _ in range ( len ( q )): node = q . popleft () self . tree . append ( node ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) def insert ( self , val : int ) -> int : pid = ( len ( self . tree ) - 1 ) >> 1 node = TreeNode ( val ) self . tree . append ( node ) p = self . tree [ pid ] if p . left is None : p . left = node else : p . right = node return p . val def get_root ( self ) -> TreeNode : return self . tree [ 0 ] # Your CBTInserter object will be instantiated and called as such: # obj = CBTInserter(root) # param_1 = obj.insert(val) # param_2 = obj.get_root()

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem