# LeetCode 623: Add One Row to Tree

## Problem Restatement

We are given the root of a binary tree and two integers `val` and `depth`.

We need to add a new row of nodes with value `val` at the given `depth`.

The root is at depth `1`.

If `depth == 1`, we create a new root with value `val`. The original tree becomes the left child of the new root.

Otherwise, for every non-null node at depth `depth - 1`:

1. Create a new left child with value `val`.
2. Create a new right child with value `val`.
3. The old left subtree becomes the left subtree of the new left child.
4. The old right subtree becomes the right subtree of the new right child.

This matches the official rule for the problem.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, `val`, and `depth` |
| Output | The root of the modified tree |
| Root depth | The original root is at depth `1` |
| Special case | If `depth == 1`, create a new root |
| Main operation | Insert new nodes below every node at depth `depth - 1` |

Example function shape:

```python
def addOneRow(root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
    ...
```

## Examples

Example 1:

```text
Input:  root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
```

Original tree:

```text
        4
       / \
      2   6
     / \ /
    3  1 5
```

We insert a row at depth `2`.

The nodes at depth `depth - 1 = 1` are just:

```text
4
```

So we add two new nodes with value `1` below `4`.

The old left subtree rooted at `2` becomes the left child of the new left `1`.

The old right subtree rooted at `6` becomes the right child of the new right `1`.

Result:

```text
        4
       / \
      1   1
     /     \
    2       6
   / \     /
  3   1   5
```

Example 2:

```text
Input:  root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]
```

Original tree:

```text
      4
     /
    2
   / \
  3   1
```

We insert at depth `3`, so we modify nodes at depth `2`.

The only node at depth `2` is `2`.

After insertion:

```text
      4
     /
    2
   / \
  1   1
 /     \
3       1
```

## First Thought: Rebuild the Whole Tree

One possible idea is to build a new tree from scratch.

We could copy every node, and when we reach the target depth, insert the new row.

This works, but it is unnecessary. The problem only requires changing parent-child pointers around one level.

We can keep the existing tree and reconnect only the nodes at depth `depth - 1`.

## Key Insight

To add a row at `depth`, we do not need to visit nodes at `depth`.

We need to visit their future parents: the nodes at depth `depth - 1`.

For each such node `cur`, save its old children:

```python
old_left = cur.left
old_right = cur.right
```

Then create the new children:

```python
cur.left = TreeNode(val)
cur.right = TreeNode(val)
```

Then reconnect the old subtrees:

```python
cur.left.left = old_left
cur.right.right = old_right
```

The left subtree stays on the left side. The right subtree stays on the right side.

## Algorithm

Handle the special case first.

If `depth == 1`:

1. Create a new node with value `val`.
2. Set its left child to the old root.
3. Return the new node.

Otherwise, use DFS from the root.

For each node, track its current depth.

When the current depth is `depth - 1`:

1. Save the old left child.
2. Save the old right child.
3. Create a new left child with value `val`.
4. Create a new right child with value `val`.
5. Attach the old left subtree to the new left child.
6. Attach the old right subtree to the new right child.
7. Stop going deeper from this node.

## Correctness

If `depth == 1`, the required operation is to create a new root whose left child is the original tree. The algorithm does exactly that, so this case is correct.

Now suppose `depth > 1`.

The DFS visits nodes while tracking their depth from the root. Therefore, when the algorithm reaches a node at depth `depth - 1`, that node is exactly one level above the row we must insert.

For each such node `cur`, the algorithm creates two new nodes with value `val` and assigns them as `cur.left` and `cur.right`. Therefore, all new nodes are placed exactly at the required depth.

The old left subtree of `cur` is saved before changing `cur.left`, then attached as the left child of the new left node. This preserves the entire original left subtree in the required position.

The old right subtree of `cur` is saved before changing `cur.right`, then attached as the right child of the new right node. This preserves the entire original right subtree in the required position.

Nodes at other depths are not changed except through these required pointer updates. Therefore the resulting tree satisfies the insertion rule.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | In the worst case, we may visit every node before reaching the target level |
| Space | `O(h)` | Recursive DFS uses call stack space proportional to tree height |

Here, `n` is the number of nodes in the tree, and `h` is the height of the tree.

For a balanced tree, `h = O(log n)`.

For a skewed tree, `h = O(n)`.

## Implementation

```python
from typing import Optional

# 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 Solution:
    def addOneRow(
        self,
        root: Optional[TreeNode],
        val: int,
        depth: int
    ) -> Optional[TreeNode]:
        if depth == 1:
            return TreeNode(val, left=root)

        def dfs(node: Optional[TreeNode], current_depth: int) -> None:
            if node is None:
                return

            if current_depth == depth - 1:
                old_left = node.left
                old_right = node.right

                node.left = TreeNode(val)
                node.right = TreeNode(val)

                node.left.left = old_left
                node.right.right = old_right
                return

            dfs(node.left, current_depth + 1)
            dfs(node.right, current_depth + 1)

        dfs(root, 1)
        return root
```

## Code Explanation

The first case handles insertion above the original root:

```python
if depth == 1:
    return TreeNode(val, left=root)
```

This creates a new root and places the old tree as its left subtree.

The helper function receives a node and its current depth:

```python
def dfs(node: Optional[TreeNode], current_depth: int) -> None:
```

If the node is missing, there is nothing to modify:

```python
if node is None:
    return
```

When we reach the parent level of the new row, we save the original children:

```python
old_left = node.left
old_right = node.right
```

This is important because assigning new children would otherwise lose access to the old subtrees.

Then we create the new row nodes:

```python
node.left = TreeNode(val)
node.right = TreeNode(val)
```

The original left subtree is attached below the new left node:

```python
node.left.left = old_left
```

The original right subtree is attached below the new right node:

```python
node.right.right = old_right
```

After inserting at this node, we return immediately:

```python
return
```

There is no need to traverse deeper, because the new row has already been inserted below this node.

If we are not yet at the parent level, DFS continues:

```python
dfs(node.left, current_depth + 1)
dfs(node.right, current_depth + 1)
```

Finally, we return the original root:

```python
return root
```

The root only changes when `depth == 1`.

## Testing

```python
from collections import deque

def build_tree(values):
    if not values or values[0] is None:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def to_list(root):
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node is None:
            result.append(None)
            continue

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

    while result and result[-1] is None:
        result.pop()

    return result

def run_tests():
    s = Solution()

    root = build_tree([4, 2, 6, 3, 1, 5])
    new_root = s.addOneRow(root, 1, 2)
    assert to_list(new_root) == [4, 1, 1, 2, None, None, 6, 3, 1, 5]

    root = build_tree([4, 2, None, 3, 1])
    new_root = s.addOneRow(root, 1, 3)
    assert to_list(new_root) == [4, 2, None, 1, 1, 3, None, None, 1]

    root = build_tree([1, 2, 3])
    new_root = s.addOneRow(root, 5, 1)
    assert to_list(new_root) == [5, 1, None, 2, 3]

    root = build_tree([1])
    new_root = s.addOneRow(root, 9, 2)
    assert to_list(new_root) == [1, 9, 9]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Insert at depth `2` | Modifies directly below the root |
| Insert at depth `3` | Preserves lower subtrees correctly |
| Insert at depth `1` | Creates a new root |
| Single-node tree | Checks adding children to a leaf |