Add One Row to Tree — BFS Insertion at Depth in O(n)

Problem Statement#

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth. The new row's nodes become parents of the original nodes at depth depth. Specifically, every original node at depth depth - 1 gains two new children with value val; the original left and right subtrees become the left and right subtrees of the new left and right children, respectively.

If depth == 1, create a new root with value val whose left subtree is the original tree.

Constraints:

• Number of nodes is in [1, 10^4]
• The depth of the tree is in [1, 10^4]
• -100 <= Node.val <= 100
• -10^5 <= val <= 10^5
• 1 <= depth <= depth of tree + 1

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

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

Why This Problem Matters#

LeetCode 623 "Add One Row to Tree" is a popular Amazon and Microsoft question for evaluating practical tree manipulation. It is structurally simple but exposes whether you reason carefully about edge cases — specifically the depth == 1 rule that prepends a new root.

The problem also tests pointer rewiring discipline: each node at the parent depth needs both children replaced, with the original left going to the new node's left, and the original right going to the new node's right. Getting this asymmetry right is the whole point.

The Core Insight#

Two approaches share the same logic:

• BFS until you reach depth depth - 1. For every node in that level, splice in two new nodes.
• DFS with a current depth counter. When depth hits depth - 1, splice.

The rewiring rule is symmetric:

• node.left = new TreeNode(val, node.left, null)
• node.right = new TreeNode(val, null, node.right)

The first new node steals the original left subtree as its own left child; the second new node steals the original right subtree as its own right child.

Special case: depth == 1 means the new node becomes the root, with the entire original tree as its left subtree.

Visual Dry Run#

Tree [4,2,6,3,1,5], val=1, depth=2. Splice at depth 1 (the root level — its children land at depth 2).

Result: [4,1,1,2,null,null,6,3,1,5].

Solution (Optimal)#

class Solution:
    def addOneRow(self, root, val, depth):
        if depth == 1:
            return TreeNode(val, root, None)
 
        from collections import deque
        queue = deque([(root, 1)])
        while queue:
            node, d = queue.popleft()
            if d == depth - 1:
                node.left = TreeNode(val, node.left, None)
                node.right = TreeNode(val, None, node.right)
            else:
                if node.left:
                    queue.append((node.left, d + 1))
                if node.right:
                    queue.append((node.right, d + 1))
        return root

var addOneRow = function(root, val, depth) {
    if (depth === 1) return new TreeNode(val, root, null);
 
    const queue = [[root, 1]];
    while (queue.length) {
        const [node, d] = queue.shift();
        if (d === depth - 1) {
            node.left = new TreeNode(val, node.left, null);
            node.right = new TreeNode(val, null, node.right);
        } else {
            if (node.left) queue.push([node.left, d + 1]);
            if (node.right) queue.push([node.right, d + 1]);
        }
    }
    return root;
};

Time: O(n) — each node is enqueued at most once. Space: O(w) — width of the tree at the deepest level (BFS frontier).

Common Mistakes#

• Putting the original left subtree under the new right node (or vice versa).
• Forgetting the depth == 1 special case — the new node is the new root.
• Splicing at depth depth instead of depth - 1. The new row's parents live one level above.
• Adding nodes only when an original child exists. Even null original children get replaced by new nodes.
• Using shift() in JavaScript on huge inputs — O(n) per call. Prefer a real queue or index pointer.

Interview Tips#

• State the rewiring rule out loud: "left of new = original left; right of new = original right."
• Cover the depth == 1 base case before the main loop.
• BFS with a depth counter is cleaner than tracking levels; use a tuple (node, depth).
• DFS works equally well — useful when interviewers ask for recursive variants.

Follow-up Questions#

• Add multiple rows: insert k rows at the same depth. Hint: chain new nodes vertically.
• Add row of varying values: values come from a list of length equal to depth-1 width. Hint: BFS while indexing.
• Remove a row: invert the operation. Hint: BFS to depth-1, replace node.left = node.left.left, node.right = node.right.right.
• Validate after insertion: check that subtree heights remain valid. Hint: post-order DFS.
• Iterative DFS: rewrite without recursion. Hint: explicit stack with depth counter.

Key Takeaways#

• LeetCode 623 is BFS-friendly: stop one level above the target depth.
• New left node steals the original left subtree; new right node steals the original right subtree.
• depth == 1 requires creating a new root and is an easy case to miss.
• Both BFS and DFS reach O(n) time and O(w) or O(h) space respectively.
• Splice both children even if originals are null — that is the contract.
• Common at Amazon and Microsoft phone screens for tree manipulation.
• Mirror question: removing a row uses the inverse rewiring.