Problem Description

A complete binary tree is a binary tree where every level is completely filled, except possibly the last level. In the last level, all nodes are positioned as far left as possible.

You need to design a data structure that maintains a complete binary tree and supports insertion operations while keeping the tree complete.

Implement the CBTInserter class with the following methods:

• CBTInserter(TreeNode root): Initialize the data structure with an existing complete binary tree rooted at root.
• int insert(int v): Insert a new node with value v into the tree while maintaining its completeness property. Return the value of the parent node of the newly inserted node.
• TreeNode get_root(): Return the root node of the tree.

The key challenge is to efficiently determine where to insert the next node to maintain the complete binary tree property. In a complete binary tree, nodes are filled level by level from left to right.

The solution uses an array-based representation where all nodes are stored in level-order (BFS) traversal order. This allows for easy parent-child relationship calculations:

• For a node at index i, its parent is at index (i-1)//2
• For a parent at index i, its left child would be at index 2*i+1 and right child at 2*i+2

During initialization, the existing tree is traversed using BFS and all nodes are stored in the array. When inserting a new node, the parent can be found at index (len(tree)-1)//2, and the new node is added as either the left or right child depending on which position is empty.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A tree is a special type of graph (acyclic connected graph). The problem explicitly deals with a binary tree structure.

Is it a tree?

• Yes: The problem specifically mentions we're working with a complete binary tree.

DFS?

• Not necessarily: While DFS could work, for a complete binary tree where we need to maintain level-order insertion (filling levels from left to right), BFS is more natural. Let's reconsider...

Actually, looking at the solution approach, it uses BFS (level-order traversal) to initialize the tree structure. The queue-based traversal in the initialization clearly indicates BFS is being used:

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)

The BFS pattern is ideal here because:

1. Level-order traversal: BFS naturally processes nodes level by level, which aligns perfectly with how a complete binary tree is structured
2. Array representation: By traversing in BFS order, nodes are stored in the array following the heap property where parent-child relationships can be calculated using indices
3. Efficient insertion: The array representation obtained from BFS allows O(1) parent finding for new insertions

Conclusion: The flowchart leads us to BFS through the tree path, as BFS is the optimal approach for maintaining and manipulating a complete binary tree structure where level-order properties are crucial.

Intuition

The key insight comes from understanding the properties of a complete binary tree. In a complete binary tree, nodes are filled level by level from left to right, which creates a very predictable pattern.

Think about how nodes are numbered in a complete binary tree if we label them in level-order (BFS) sequence starting from 0:

• Root is at index 0
• For any node at index i, its left child is at index 2*i + 1 and right child is at 2*i + 2
• For any node at index i, its parent is at index (i-1) // 2

This mathematical relationship is exactly like a heap data structure! This means we can represent the entire tree as an array where the position in the array determines the parent-child relationships.

When we need to insert a new node while maintaining completeness, we know it must go at the next available position in level-order. If we maintain all nodes in an array following BFS order, the next insertion position is simply the next index in the array.

To find the parent of this new node, we use the formula (len(array) - 1) // 2. Why does this work? Because if the new node will be at index n, its parent is at index (n-1) // 2. Since we haven't added the node yet, n = len(array), so the parent is at (len(array) - 1) // 2.

The initialization uses BFS to convert the existing tree into this array representation. Once we have this array, insertions become trivial - just append to the array and connect to the parent node. We can determine whether the new node should be a left or right child by checking if the parent already has a left child.

This approach brilliantly transforms a tree manipulation problem into simple array operations with O(1) insertion complexity.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution uses an array-based representation of the complete binary tree, leveraging BFS for initialization and mathematical indexing for efficient insertions.

Initialization (__init__)

We use BFS to traverse the existing complete binary tree and store all nodes in an array self.tree:

1. Create an empty array self.[tree](/problems/tree_intro) to store all nodes
2. Initialize a queue with the root node
3. Process nodes level by level using BFS:
   • For each level, process all nodes in the queue
   • Add each node to self.tree array
   • Add the node's children (if they exist) to the queue for the next level

q = deque([root])
while q:
    for _ in range(len(q)):
        node = q.popleft()
        self.[tree](/problems/tree_intro).append(node)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

After initialization, self.[tree](/problems/tree_intro) contains all nodes in level-order sequence.

Insertion (insert)

To insert a new node while maintaining completeness:

1. Calculate the parent node's index: p = self.[tree](/problems/tree_intro)[(len(self.tree) - 1) // 2]

   • If the new node will be at index n, its parent is at (n-1) // 2
   • Since n = len(self.tree) (before insertion), parent index is (len(self.tree) - 1) // 2

2. Create the new node: node = TreeNode(val)

3. Append the new node to the array: self.[tree](/problems/tree_intro).append(node)

4. Connect the new node to its parent:

   • If parent has no left child, make the new node the left child
   • Otherwise, make it the right child

5. Return the parent's value

Get Root (get_root)

Simply return the first element of the array: return self.[tree](/problems/tree_intro)[0]

Time and Space Complexity

• Initialization: O(n) time and O(n) space, where n is the number of nodes in the initial tree
• Insertion: O(1) time for each insertion
• Get Root: O(1) time

The beauty of this approach is that it transforms tree operations into simple array operations by maintaining the heap property, where parent-child relationships are determined by array indices rather than explicit pointers.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Initial tree:

       1
      / \
     2   3
    /
   4

Step 1: Initialization with CBTInserter(root)

We perform BFS traversal to build our array representation:

• Start with queue = [1]
• Process level 1: Add node 1 to array, queue becomes [2, 3]
• Process level 2: Add nodes 2 and 3 to array, queue becomes [4]
• Process level 3: Add node 4 to array, queue becomes empty

Result: self.tree = [1, 2, 3, 4] (nodes stored by reference, showing values for clarity)

The array indices correspond to:

• Index 0: node 1 (root)
• Index 1: node 2 (left child of 1)
• Index 2: node 3 (right child of 1)
• Index 3: node 4 (left child of 2)

Step 2: Insert value 5

1. Calculate parent index: (len(self.tree) - 1) // 2 = (4 - 1) // 2 = 1

   • Parent is at index 1, which is node 2

2. Create new node with value 5

3. Append to array: self.tree = [1, 2, 3, 4, 5]

4. Connect to parent:

   • Node 2 already has a left child (node 4)
   • So make node 5 the right child of node 2

5. Return parent value: 2

Tree after insertion:

       1
      / \
     2   3
    / \
   4   5

Step 3: Insert value 6

1. Calculate parent index: (5 - 1) // 2 = 2

   • Parent is at index 2, which is node 3

2. Create new node with value 6

3. Append to array: self.tree = [1, 2, 3, 4, 5, 6]

4. Connect to parent:

   • Node 3 has no left child
   • So make node 6 the left child of node 3

5. Return parent value: 3

Final tree:

       1
      / \
     2   3
    / \ /
   4  5 6

The array [1, 2, 3, 4, 5, 6] perfectly represents the complete binary tree, where:

• Node at index i has parent at index (i-1)//2
• Node at index i has left child at index 2i+1 and right child at index 2i+2

This demonstrates how the array-based approach elegantly maintains the complete binary tree property with O(1) insertions.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Initialization (__init__): O(n) where n is the number of nodes in the initial tree. The constructor performs a level-order traversal using BFS to visit all nodes exactly once and append them to the self.tree list.

• Insert (insert): O(1). The method calculates the parent index using the formula (len(self.tree) - 1) // 2, creates a new node, appends it to the list, and updates the parent's child pointer. All these operations take constant time.

• Get Root (get_root): O(1). Simply returns the first element of the self.tree list, which is a constant time operation.

Space Complexity:

• O(n) where n is the total number of nodes in the tree. The self.tree list stores references to all nodes in the complete binary tree. Additionally, during initialization, the BFS queue temporarily holds at most O(n) nodes in the worst case (though typically much less for a complete binary tree where the last level contains about half the nodes).

The key insight is that by maintaining all nodes in an array representation of the complete binary tree, we can leverage the mathematical relationship between parent and child indices (parent at index i has children at indices 2i+1 and 2i+2) to achieve constant-time insertions while preserving the complete binary tree property.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Parent Index Calculation

A common mistake is using the wrong formula for finding the parent index, especially when dealing with 0-indexed vs 1-indexed arrays.

Pitfall Example:

# Wrong: Using 1-indexed formula in 0-indexed array
parent_index = len(self.tree_nodes) // 2  # Missing the -1

# Wrong: Off-by-one error
parent_index = (len(self.tree_nodes)) // 2  # Should be (len - 1) // 2

Correct Approach:

# For 0-indexed array where new node will be at index len(tree_nodes)
parent_index = (len(self.tree_nodes) - 1) // 2

2. Not Handling Empty Tree Initialization

The code assumes the root is never None, but this could cause issues if an empty tree is passed.

Pitfall Example:

def __init__(self, root: Optional[TreeNode]):
    self.tree_nodes = []
    queue = deque([root])  # If root is None, this adds None to queue
    while queue:
        # Will process None and cause errors

Solution:

def __init__(self, root: Optional[TreeNode]):
    self.tree_nodes = []
    if root is None:
        return
    queue = deque([root])
    # ... rest of the BFS code

3. Forgetting to Update Parent's Child Pointers

A critical mistake is adding the new node to the array but forgetting to update the parent node's left/right pointers.

Pitfall Example:

def insert(self, val: int) -> int:
    parent_index = (len(self.tree_nodes) - 1) // 2
    parent_node = self.tree_nodes[parent_index]
    new_node = TreeNode(val)
    self.tree_nodes.append(new_node)
    # Forgot to set parent_node.left or parent_node.right!
    return parent_node.val

4. Using Wrong Data Structure for Level-Order Traversal

Using a list instead of deque for BFS can lead to inefficient O(n) operations when removing from the front.

Pitfall Example:

# Inefficient: Using list.pop(0) is O(n)
queue = [root]
while queue:
    node = queue.pop(0)  # O(n) operation

Better Approach:

# Efficient: Using deque.popleft() is O(1)
queue = deque([root])
while queue:
    node = queue.popleft()  # O(1) operation

5. Misunderstanding the Parent-Child Relationship

Confusion about when to attach as left vs right child, especially with the array indexing approach.

Key Understanding:

• In a 0-indexed array representation:
  • Node at index i has left child at 2*i + 1 and right child at 2*i + 2
  • When inserting at position n, if n is odd, it's a left child; if even, it's a right child

Reliable Check:

if parent_node.left is None:
    parent_node.left = new_node
else:
    parent_node.right = new_node

This approach is more reliable than trying to determine left/right based on the index arithmetic.