Add One Row to Tree: BFS Insertion at a Target Depth

May 20, 20266 min read

leetcodeproblemmediumtrees

Given the root of a binary tree and two integers val and depth, you need to add a row of nodes with value val at the given depth. This is LeetCode 623: Add One Row to Tree, and it tests your ability to traverse to a specific level and rewire parent-child relationships cleanly.

Tree [4,2,6,3,1,5] with val=1 and depth=2. New nodes (green) are inserted at depth 2. Original children shift down one level.

The key insight is that you do not insert nodes at the target depth directly. Instead, you find every node at depth - 1 and give each one new children. The new nodes inherit the old subtrees: the new left child takes over the original left subtree, and the new right child takes over the original right subtree.

Why BFS works well here

You need to reach a specific level in the tree. BFS (breadth-first search) naturally processes nodes level by level using a queue, so you can count levels as you go and stop exactly when you hit depth - 1. At that point, every node in the queue is a parent that needs new children inserted.

DFS can also solve this problem (more on that below), but BFS makes the "find all nodes at level X" operation explicit and easy to reason about.

The BFS solution

from collections import deque

def add_one_row(root, val, depth):
    if depth == 1:
        new_root = TreeNode(val)
        new_root.left = root
        return new_root

    queue = deque([root])
    current_depth = 1

    while current_depth < depth - 1:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        current_depth += 1

    while queue:
        node = queue.popleft()
        old_left = node.left
        old_right = node.right
        node.left = TreeNode(val)
        node.left.left = old_left
        node.right = TreeNode(val)
        node.right.right = old_right

    return root

Here is what each part does:

depth == 1 guard: When the new row goes at the very top, you create a new root with value val and attach the entire original tree as its left child. This is a special case because there is no "parent" above the root.
Level traversal loop: The first while loop runs BFS level by level, stopping when current_depth reaches depth - 1. After this loop, the queue holds exactly the nodes that need new children.
Insertion loop: The second while loop processes each parent. It saves the old left and right children, creates new nodes with val, and wires the old subtrees under the new nodes. The left new node gets the old left subtree as its left child. The right new node gets the old right subtree as its right child.

The rewiring pattern is always the same: new_left.left = old_left and new_right.right = old_right. The new nodes act as "shims" that push the original subtrees one level deeper without changing their internal structure.

Practice tree insertion with spaced repetition

Visual walkthrough

Let's trace the algorithm through the tree [4, 2, 6, 3, 1, 5] with val = 1 and depth = 2. We need to find all nodes at depth 1 (the root) and insert new children.

Step 1: Handle edge case. Check if depth equals 1.

If depth is 1, create a new root with the given value. Attach the entire original tree as the left child of the new root and return it. No traversal needed.

Step 2: Initialize BFS. Push the root into a queue.

We need to find all nodes at depth-1 (one level above where the new row goes). Start BFS from the root at level 1. The queue holds nodes from the current level.

Step 3: Traverse levels until we reach depth-1.

Process one level at a time. At each level, dequeue all current nodes and enqueue their children. Keep a level counter. When the counter reaches depth-1, stop enqueuing and move to the insertion step.

Step 4: Insert new nodes. For each node at depth-1, rewire children.

For each parent node at depth-1: create a new TreeNode(val) as the new left child, and set its left child to the parent's old left child. Create another new TreeNode(val) as the new right child, and set its right child to the parent's old right child.

Step 5: Done. Return the original root.

The tree now has a new row of nodes at the target depth. Each new node inherited exactly one subtree from its parent: left children keep the old left subtree, right children keep the old right subtree.

The process is mechanical. Traverse to the right level, save old children, insert new nodes, and rewire. No recursion, no backtracking, just a clean level-by-level scan followed by pointer surgery.

Recursive DFS approach

If you prefer recursion, you can solve this with a DFS that tracks the current depth. When you reach depth - 1, insert new nodes and return without recursing further.

def add_one_row_dfs(root, val, depth):
    if depth == 1:
        new_root = TreeNode(val)
        new_root.left = root
        return new_root

    def dfs(node, current_depth):
        if not node:
            return
        if current_depth == depth - 1:
            old_left = node.left
            old_right = node.right
            node.left = TreeNode(val)
            node.left.left = old_left
            node.right = TreeNode(val)
            node.right.right = old_right
            return
        dfs(node.left, current_depth + 1)
        dfs(node.right, current_depth + 1)

    dfs(root, 1)
    return root

The DFS version has the same time and space complexity. It visits every node down to depth depth - 1 and stops. The recursive call stack uses O(d) space where d is the target depth, while BFS uses O(w) space where w is the width of the level. Pick whichever feels more natural to you.

Drill tree traversal patterns on CodeBricks

Complexity analysis

Metric	Value	Why
Time	O(n)	In the worst case, you visit every node in the tree (when depth equals the tree height)
Space	O(w) for BFS, O(d) for DFS	BFS queue holds at most one level (width w). DFS call stack goes at most d levels deep

Both approaches are O(n) time in the worst case. The space difference depends on the tree shape. For a wide, balanced tree, BFS uses more space. For a deep, skinny tree, DFS uses more space. In practice, either is fine.

Building blocks

This problem combines two fundamental patterns:

BFS level-by-level traversal. The standard BFS template uses a queue and a level-size snapshot to process one level at a time. You use this whenever a problem says "at depth X" or "at level X."

from collections import deque

def bfs_to_level(root, target_level):
    queue = deque([root])
    level = 1
    while level < target_level:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        level += 1
    return queue

Tree node insertion (rewiring children). Inserting a node into a tree means updating parent pointers. You save the old child reference, create a new node, attach it to the parent, and then attach the old child under the new node. This pattern appears in linked list insertion problems too.

Once you are comfortable with both of these building blocks, "Add One Row to Tree" is just the two of them combined.

Edge cases

depth equals 1: The new row becomes the new root. The entire original tree hangs off the new root's left child. This is the only case where the root changes.
Single-node tree with depth equals 2: The root gets two new children with value val. Both new children are leaves (their subtrees are null since the original root had no children).
depth equals the height + 1: The new row is added as leaves at the very bottom. Every leaf node at the current bottom level gets two new children.
Unbalanced tree: Some nodes at depth - 1 may have children on only one side or no children at all. The algorithm still works because it always creates both a new left and a new right child, assigning null as the subtree when the original child was missing.

From understanding to recall

You just worked through a clean BFS-based insertion and saw how the rewiring pattern keeps the tree structure intact. It makes sense right now. But will you remember the depth - 1 targeting and the new_left.left = old_left wiring pattern when a similar problem shows up in an interview?

Reading through a solution and being able to reproduce it from memory are two different skills. Spaced repetition bridges that gap. You practice the BFS-to-level template and the node insertion pattern at increasing intervals until they become automatic. First after a day, then three days, then a week.

"Add One Row to Tree" exercises two building blocks that show up across many tree problems. Drilling them individually is more effective than grinding random problems and hoping the connections stick.

Binary Tree Level Order Traversal - The definitive guide to BFS level-by-level processing, which is the foundation for reaching a target depth
Maximum Depth of Binary Tree - Builds intuition for tree depth and recursion, useful context for understanding what "depth" means in tree problems
Binary Tree Right Side View - Another BFS-by-level problem where you process nodes at each depth, reinforcing the same traversal template

Try CodeBricks free