Is Complete Binary Tree Inserter easy or hard?

Complete Binary Tree Inserter is rated Medium difficulty on LeetCode with an acceptance rate around 65%. The challenge is recognizing that you should maintain a queue of incomplete nodes instead of scanning the tree every time you insert.

Complete Binary Tree Inserter Python/Java solution

Python solutions typically use collections.deque to maintain the candidate parent queue. Java implementations commonly use a LinkedList or ArrayDeque for the same BFS queue structure. Both languages implement the same logic: preprocess the tree, then perform O(1) insert operations.

How to solve Complete Binary Tree Inserter in O(n)?

Run a level-order traversal to find the first node missing a child and insert there. If you repeat this traversal for every insert, the operation costs O(n) time. A more efficient design precomputes candidate parents using BFS so that later insertions become O(1).

What is the best approach for Complete Binary Tree Inserter?

The optimal approach maintains a queue of nodes that are missing at least one child. During initialization, perform a BFS to populate this queue. Each insertion attaches the new node to the front node in the queue and updates the queue accordingly. This design gives O(1) insertion time after an O(n) preprocessing step.

Is Complete Binary Tree Inserter asked at Google/Amazon/Meta?

Tree design and BFS-based insertion problems appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of complete binary tree properties, queue-based traversal, and data structure design patterns.

What data structure is used in Complete Binary Tree Inserter?

The core data structure is a queue used for breadth-first traversal. The queue stores nodes that do not yet have two children, allowing constant-time access to the next valid parent during insertion. The tree itself is represented using standard binary tree nodes.

What is the time complexity of Complete Binary Tree Inserter?

Using the optimized BFS queue design, initialization takes O(n) time to scan the existing tree. Each insert operation runs in O(1) time because the next valid parent is already tracked in a queue. Space complexity is O(n) for storing candidate parent nodes.

Description Solution Video 21:59

919. Complete Binary Tree Inserter

Medium65.0% acceptance3 companies

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.

Asked at 3 companies

Google Amazon Meta

Topics

21:59

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class CBTInserter:
8 
9    def __init__(self, root: Optional[TreeNode]):
10        
11 
12    def insert(self, val: int) -> int:
13        
14 
15    def get_root(self) -> Optional[TreeNode]:
16        
17 
18 
19# Your CBTInserter object will be instantiated and called as such:
20# obj = CBTInserter(root)
21# param_1 = obj.insert(val)
22# param_2 = obj.get_root()

Starter codePython 3Spaces: 4

Examples

Case 1

Input

["CBTInserter","insert","insert","get_root"]
[[[1,2]],[3],[4],[]]

Your code is saved on this device.Solution