LeetCode 919: Complete Binary Tree Inserter

Problem Restatement

We need to design a class called CBTInserter.

It is initialized with the root of a complete binary tree.

A complete binary tree has every level full except possibly the last level, and the last level is filled from left to right.

The class must support:

Method	Meaning
`CBTInserter(root)`	Initialize with an existing complete binary tree
`insert(val)`	Insert a new node while keeping the tree complete, and return the parent value
`get_root()`	Return the root node

The inserted node must go into the next available position in level-order. The official statement defines this complete-tree insertion rule.

Input and Output

Item	Meaning
Constructor input	Root of a complete binary tree
`insert(val)` input	Value for the new node
`insert(val)` output	Value of the parent node
`get_root()` output	Root of the tree

Class shape:

class CBTInserter:

    def __init__(self, root: TreeNode):
        ...

    def insert(self, val: int) -> int:
        ...

    def get_root(self) -> TreeNode:
        ...

Examples

Example:

root = [1, 2]

cBTInserter = CBTInserter(root)

cBTInserter.insert(3)  # returns 1
cBTInserter.insert(4)  # returns 2
cBTInserter.get_root() # returns [1, 2, 3, 4]

Start:

    1
   /
  2

Insert 3.

The next open position is the right child of 1:

    1
   / \
  2   3

Return parent value:

Insert 4.

The next open position is the left child of 2:

Return parent value:

First Thought: Search for the Next Open Node Every Time

A direct method is to run BFS every time insert is called.

The first node found with a missing child is the insertion parent.

from collections import deque

class CBTInserter:

    def __init__(self, root: TreeNode):
        self.root = root

    def insert(self, val: int) -> int:
        queue = deque([self.root])

        while queue:
            node = queue.popleft()

            if not node.left:
                node.left = TreeNode(val)
                return node.val

            if not node.right:
                node.right = TreeNode(val)
                return node.val

            queue.append(node.left)
            queue.append(node.right)

    def get_root(self) -> TreeNode:
        return self.root

This is correct but inefficient.

Each insertion may scan many nodes again.

Key Insight

A complete binary tree has the same structure as an array-based heap.

If we store all nodes in level-order, then:

Node index	Relationship
`i`	Current node
`(i - 1) // 2`	Parent index
`2 * i + 1`	Left child index
`2 * i + 2`	Right child index

So insertion becomes simple.

If the current tree has n nodes, the new node will be placed at index n.

Its parent is:

(n - 1) // 2

If n is odd, the new node is a left child.

If n is even, the new node is a right child.

This works because level-order array indexing matches complete binary tree filling order.

Algorithm

Constructor:

Store the root.
Run BFS from the root.
Store every node in an array in level-order.

Insert:

Let n = len(nodes).
Create the new node.
Find the parent at index (n - 1) // 2.
If n is odd, attach the new node as parent.left.
Otherwise, attach it as parent.right.
Append the new node to the array.
Return parent.val.

Get root:

Return the stored root.

Correctness

The constructor stores nodes in level-order.

Since the input tree is complete, this array order is exactly the same order used by complete binary tree insertion.

Before each insertion, suppose the array contains all current tree nodes in level-order.

The next inserted node must occupy the next level-order position, which is index n, where n is the current number of nodes.

In an array representation of a complete binary tree, the parent of index n is (n - 1) // 2.

If n is odd, it is the left child position. If n is even, it is the right child position.

The algorithm attaches the new node exactly there, so the tree remains complete.

After appending the new node to the array, the array again contains all nodes in level-order.

By induction, every insertion preserves the complete binary tree property.

Complexity

Operation	Time	Space
Constructor	`O(n)`	`O(n)`
`insert(val)`	`O(1)`	`O(1)` extra
`get_root()`	`O(1)`	`O(1)`

The constructor stores all nodes once.

Each insertion computes the parent index directly.

Implementation

from collections import deque

# 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.root = root
        self.nodes = []

        queue = deque([root])

        while queue:
            node = queue.popleft()
            self.nodes.append(node)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

    def insert(self, val: int) -> int:
        n = len(self.nodes)

        node = TreeNode(val)
        parent = self.nodes[(n - 1) // 2]

        if n % 2 == 1:
            parent.left = node
        else:
            parent.right = node

        self.nodes.append(node)

        return parent.val

    def get_root(self) -> TreeNode:
        return self.root

Code Explanation

Store the original root:

self.root = root

Store nodes in level-order:

self.nodes = []

The constructor uses BFS:

queue = deque([root])

Every popped node is appended to the array:

node = queue.popleft()
self.nodes.append(node)

For insertion, the new node’s index will be the current length:

n = len(self.nodes)

Find the parent directly:

parent = self.nodes[(n - 1) // 2]

Attach as left child when n is odd:

if n % 2 == 1:
    parent.left = node

Attach as right child when n is even:

else:
    parent.right = node

Finally, append the node to preserve level-order storage:

self.nodes.append(node)

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)

    return result

def run_tests():
    root = TreeNode(1, TreeNode(2))

    inserter = CBTInserter(root)

    assert inserter.insert(3) == 1
    assert inserter.insert(4) == 2
    assert level_order(inserter.get_root()) == [1, 2, 3, 4]

    root = TreeNode(
        10,
        TreeNode(20),
        TreeNode(30),
    )

    inserter = CBTInserter(root)

    assert inserter.insert(40) == 20
    assert inserter.insert(50) == 20
    assert inserter.insert(60) == 30
    assert level_order(inserter.get_root()) == [10, 20, 30, 40, 50, 60]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Root with one left child	Matches the sample behavior
Several insertions	Checks left-to-right filling order
`get_root()`	Confirms the original tree is updated
Level-order output	Verifies complete tree structure