623 · Add One Row to Tree

The only problem in this pattern that changes the tree rather than reading it. The traversal itself is trivial — walk down to a given depth — and all the difficulty is in the two lines that re-attach the existing subtrees, plus one special case at the top.

1 — The rule

Insert a new row of nodes, all holding val, at depth depth. The root is depth 1. Every node currently at depth depth - 1 gets two new children, and:

• its original left subtree becomes the new left node's left child;
• its original right subtree becomes the new right node's right child.

Left stays left and right stays right. Attaching an old subtree to the wrong side of the new node still produces a valid tree and still passes a shape check — it just quietly mirrors part of the answer, which makes it an unusually annoying bug to spot.

2 — Inserting a row

root = [4,2,6,3,1,5], val = 1, depth = 2. The parents are at depth 1, so that is just the root itself. The diagram is re-laid-out on every frame, so you can watch the tree physically grow.

if (depth == 1)    return new TreeNode(val, root, null);List<TreeNode> row = List.of(root);for (int d = 1; d < depth - 1; d++)    row = childrenOf(row);            // walk down to depth - 1for (TreeNode p : row) {    p.left  = new TreeNode(val, p.left, null);    p.right = new TreeNode(val, null, p.right);}return root;

3 — The special case: depth 1

There is no depth 0, so there are no parents to edit. The new node becomes the root and the entire old tree hangs off its left.

if (depth == 1)    return new TreeNode(val, root, null);List<TreeNode> row = List.of(root);for (int d = 1; d < depth - 1; d++)    row = childrenOf(row);            // walk down to depth - 1for (TreeNode p : row) {    p.left  = new TreeNode(val, p.left, null);    p.right = new TreeNode(val, null, p.right);}return root;

Handle this before the walk begins. If you don't, the loop looks for nodes at depth 0, finds none, and returns the tree untouched — a silent wrong answer rather than a crash.

4 — Complexity and edge cases

• Time: O(n) — you touch each node above the insertion depth once, and each parent once more.
• Space: O(w) for the BFS frontier, or O(h) if you recurse. The new nodes themselves are O(number of parents).
• depth == 1 is the special case above, and it is the entire trick of the problem.
• A node at depth depth - 1 with a missing child still gets both new children — the new node's own child is simply null. Do not skip null branches when creating the row; only when descending to find it.
• depth exceeds the tree height: the constraints guarantee the depth is reachable, so the parent row is never empty. If you generalise, an empty row means nothing to do.
• Recursive version: stop at depth == 2 and splice from there. Some find it cleaner; it is the same two lines either way.

5 — Reference implementation

public TreeNode addOneRow(TreeNode root, int val, int depth) {
    if (depth == 1) return new TreeNode(val, root, null);

    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    for (int d = 1; d < depth - 1; d++) {   // walk down to depth - 1
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
    }
    for (TreeNode p : q) {                    // every parent gets BOTH children
        p.left  = new TreeNode(val, p.left, null);   // old left stays LEFT
        p.right = new TreeNode(val, null, p.right);  // old right stays RIGHT
    }
    return root;
}

A recursive alternative, if you prefer it: if (depth == 1) return new TreeNode(val, root, null); then if (root == null) return null; and recurse into both children with depth - 1, splicing when depth == 2. Same work, fewer moving parts than managing an explicit frontier.