Skip to main content

623 - Add One Row to Tree

Difficulty: Medium | Pattern: Tree BFS/DFS | Company tags: Amazon, Google

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 depth.

Note that the root node is at depth 1.

The adding rule is:

  • For each not-null tree node at depth depth - 1, create two nodes with value val as the new left and right children.
  • The node's original left subtree should be the left subtree of the new left child.
  • The node's original right subtree should be the right subtree of the new right child.

If depth == 1, create a new root node with value val and the original tree as its left child.

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]

Solution: BFS Level Order — O(n), O(w)​

from collections import deque

def addOneRow(root, val: int, depth: int):
    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()
        new_left = TreeNode(val)
        new_right = TreeNode(val)
        new_left.left = node.left
        new_right.right = node.right
        node.left = new_left
        node.right = new_right
    
    return root

Dry Run​

root=[4,2,6], val=1, depth=2

BFS reaches depth 1 (root=4):

  • Create new_left(1) with left=2, new_right(1) with right=6
  • root.left=new_left, root.right=new_right

Result: 4 → left:1(left=2), right:1(right=6) ✓

Edge Cases​

  • depth == 1: create new root, attach old tree as left child
  • depth > height: adds leaf nodes with no children

Complexity​

  • Time: O(n)
  • Space: O(w) — BFS queue width