#919

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Complete Binary Tree Inserter

Implement a data structure to insert nodes into a complete binary tree while preserving its completeness efficiently.

tree breadth first search design binary tree

Problem Statement

You are asked to design a data structure that allows insertion into a complete binary tree while ensuring the tree remains complete after each insertion. A complete binary tree is one where every level, except possibly the last, is fully filled, and all nodes are positioned as far left as possible.

Implement the CBTInserter class with the following methods: CBTInserter(TreeNode root) initializes the inserter with an existing complete binary tree; insert(int val) inserts a new node and returns the parent node's value; get_root() returns the root of the tree. Your implementation should efficiently handle multiple insertions while maintaining the complete tree structure.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 104 calls will be made to insert and get_root.

Solution Approach

Preprocess Existing Tree

Use a breadth-first search to traverse the tree level by level, identifying nodes that are missing children. Store nodes with available child slots in a queue to efficiently determine where the next insertion should occur.

Insertion Logic

Insert a new node as a left or right child of the first node in the queue. If the parent node now has two children, remove it from the queue. Add the new node to the queue as a potential parent for future insertions, ensuring left-to-right order is maintained.

Retrieve Root Efficiently

Keep a reference to the root node throughout insertions to allow get_root() to return the tree without additional traversal. This ensures O(1) access to the root regardless of tree size.

Complexity Analysis

Metric	Value
Time	The preprocessing is
Space	O(N_{\text{cur}})

Preprocessing the initial tree requires O(N) time and O(N) space to store nodes with available child slots. Each insertion operates in O(1) time, as the queue provides immediate access to the correct parent. Space usage scales with the number of nodes that may accept children, bounded by O(N).

What Interviewers Usually Probe

Candidate recognizes the need for BFS to track insertion points efficiently.
Candidate maintains left-to-right order at the last level, showing understanding of completeness requirements.
Candidate correctly handles updates to the parent queue after each insertion.

Common Pitfalls or Variants

Common pitfalls

Failing to maintain the queue of potential parents leads to incorrect insertion order.
Incorrectly updating parent nodes can violate completeness when multiple insertions occur.
Re-traversing the tree for each insert increases time complexity unnecessarily.

Follow-up variants

Implement a Complete Binary Tree Inserter supporting deletion while maintaining completeness.
Design a variant where insertions must also balance the tree height as much as possible.
Extend to allow batch insertions of multiple values while preserving BFS order and completeness.

FAQ

What is the key pattern to solve Complete Binary Tree Inserter efficiently?

Use a breadth-first search to maintain a queue of nodes with available child positions, ensuring insertions preserve left-to-right order.

How do I maintain the complete tree property after insertions?

Always insert at the first node in the queue with a missing child, and update the queue to track new potential parents.

Can I retrieve the root without traversing the tree each time?

Yes, by keeping a reference to the root node, get_root() can return it in O(1) time regardless of tree size.

What are common mistakes when implementing CBTInserter?

Failing to maintain the queue or incorrectly updating parent nodes can break the complete binary tree property.

Does this approach scale for multiple insertions?

Yes, each insertion operates in O(1) time using the queue, while preprocessing is O(N), making it efficient for many operations.

terminal

Solution

Solution 1: BFS

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

# 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: Optional[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:
        p = self.tree[(len(self.tree) - 1) // 2]
        node = TreeNode(val)
        self.tree.append(node)
        if p.left is None:
            p.left = node
        else:
            p.right = node
        return p.val

    def get_root(self) -> Optional[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()

Continue Practicing

#1261 find elements in a contaminated binary tree #449 serialize and deserialize bst #297 serialize and deserialize binary tree