Coding Interview PatternsAdd One Row to Tree
MediumTree Breadth-First Search

Add One Row to Tree

Explanation & Solution

Practice Problem

Description

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.

Note that the root node is at depth 1.

The adding rule is:

  • Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
  • cur's original left subtree should be the left subtree of the new left subtree root.
  • cur's original right subtree should be the right subtree of the new right subtree root.
  • If depth == 1, that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

Examples

Example 1:

```tree

[4, 2, 6, 3, 1, 5]

`

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

Explanation: At depth 1 we have node 4. We add new nodes with value 1 at depth 2. The original left subtree [2,3,1] becomes the left child of the new left node, and the original right subtree [6,5] becomes the right child of the new right node.

Example 2:

```tree

[4, 2, null, 3, 1]

`

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

Explanation: At depth 2 we have node 2. We add new nodes with value 1 at depth 3.

Example 3:

Input:root = [1], val = 5, depth = 1
0
1
Output:[5, 1]
0
5
1
1

Explanation: Since depth is 1, we create a new root with value 5, and the original tree becomes its left subtree.

Constraints

  • The number of nodes in the tree is in the range [1, 10⁴]
  • The depth of the tree is in the range [1, 10⁴]
  • -100 <= Node.val <= 100
  • -10⁵ <= val <= 10⁵
  • 1 <= depth <= the depth of tree + 1

Approach

Tree Breadth-First Search pattern

1. Handle depth = 1

  • If depth === 1:
  • Create a new root node with value val
  • Set the original tree as its left subtree
  • Return the new root
  • Reason:
  • There is no depth 0, so we handle this as a special case

2. Initialize BFS

  • Create a queue with the root node
  • Set currentDepth = 1

3. Traverse to depth - 1

  • While the queue is not empty:
  • Record the levelSize
  • If currentDepth === depth - 1, we've found the target level

4. Insert New Row

  • For each node at depth - 1:
  • Save its original left and right children
  • Create a new left child with value val, whose left child is the original left subtree
  • Create a new right child with value val, whose right child is the original right subtree

5. Continue BFS if not at target

  • If current depth is not depth - 1:
  • Process all nodes at this level
  • Enqueue their children
  • Increment currentDepth

6. Return Result

  • After inserting the new row, return the original root

Key Insight

  • BFS naturally processes nodes level by level, making it easy to find all nodes at a specific depth
  • We stop one level before the target depth to insert new nodes
Time
O(n)visit nodes up to the target depth
Space
O(w)where w is the maximum width of the tree

Visualization

Input:
DFS Traversal[4, 2, 6, 3, 1, 5]
426315
output0

Press play to start DFS traversal

CurrentIn stackComplete
13 steps

Solution Code

Previous
Check Completeness of a Binary Tree
Next
Deepest Leaves Sum