Watch 10 video solutions for Add One Row to Tree, a medium level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by codestorywithMIK has 12,151 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.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.
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]
Example 2:
Input: root = [4,2,null,3,1], val = 1, depth = 3 Output: [4,2,null,1,1,3,null,null,1]
Constraints:
[1, 104].[1, 104].-100 <= Node.val <= 100-105 <= val <= 1051 <= depth <= the depth of tree + 1Problem Overview: You are given the root of a binary tree, a value val, and a depth d. Insert a new row of nodes with value val at depth d. For every node currently at depth d-1, create two new nodes and attach the original children under them. If d = 1, the new node becomes the root and the existing tree becomes its left child.
Approach 1: Recursive Depth-First Traversal (O(n) time, O(h) space)
Use recursion to traverse the binary tree while tracking the current depth. When you reach nodes at depth d-1, create two new nodes with value val. The original left subtree becomes the left child of the new left node, and the original right subtree becomes the right child of the new right node. This works well because DFS naturally explores the structure while keeping the recursion stack limited to the tree height h. Space complexity is O(h) due to the recursion stack.
Approach 2: Iterative Breadth-First Traversal (O(n) time, O(w) space)
Perform a level-order traversal using a queue, a classic Breadth-First Search. Push the root into the queue and iterate level by level until you reach depth d-1. At that level, process each node in the queue: create two new nodes with value val, connect them as the node's new children, and reattach the original children beneath them. BFS is intuitive here because you directly move level by level, making it easy to stop exactly at the target depth.
Approach 3: Level Order BFS with Early Stop (O(n) time, O(w) space)
This variation of tree traversal uses the same queue-based level-order strategy but stops traversal once depth d-1 is reached. Instead of continuing to explore the rest of the tree, you only modify nodes in the queue at that level. This avoids unnecessary traversal and keeps the implementation clean. Space complexity is proportional to the maximum width w of the tree because the queue stores nodes from one level at a time.
Recommended for interviews: Both DFS and BFS run in O(n) time because every node may be visited once. Interviewers often prefer the BFS approach since it maps directly to the problem's “insert at depth” requirement. The recursive DFS solution demonstrates strong understanding of Depth-First Search and tree manipulation, which also makes it a solid interview answer. Showing both approaches proves you understand traversal tradeoffs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Traversal | O(n) | O(h) | When recursion is preferred and tree height is manageable |
| Iterative Breadth-First Traversal | O(n) | O(w) | Best when you want direct control over levels in the tree |
| Level Order BFS with Early Stop | O(n) | O(w) | Clean solution when modifying nodes only at a specific depth |