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

Example function shape:

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

Examples

Example 1:

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:

        4
       / \
      2   6
     / \ /
    3  1 5

We insert a row at depth 2.

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

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:

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

Example 2:

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

Original tree:

      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:

      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:

old_left = cur.left
old_right = cur.right

Then create the new children:

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

Then reconnect the old subtrees:

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

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

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:

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:

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

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

if node is None:
    return

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

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:

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

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

node.left.left = old_left

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

node.right.right = old_right

After inserting at this node, we return immediately:

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:

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

Finally, we return the original root:

return root

The root only changes when depth == 1.

Testing

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: