# 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:

```python
class CBTInserter:

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

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

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

## Examples

Example:

```python
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:

```python
    1
   /
  2
```

Insert `3`.

The next open position is the right child of `1`:

```python
    1
   / \
  2   3
```

Return parent value:

```python
1
```

Insert `4`.

The next open position is the left child of `2`:

```python
    1
   / \
  2   3
 /
4
```

Return parent value:

```python
2
```

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

```python
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:

```python
(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:

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

Insert:

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

Get root:

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

```python
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:

```python
self.root = root
```

Store nodes in level-order:

```python
self.nodes = []
```

The constructor uses BFS:

```python
queue = deque([root])
```

Every popped node is appended to the array:

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

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

```python
n = len(self.nodes)
```

Find the parent directly:

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

Attach as left child when `n` is odd:

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

Attach as right child when `n` is even:

```python
else:
    parent.right = node
```

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

```python
self.nodes.append(node)
```

## Testing

```python
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 |