Add One Row to Tree
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree and two integers val and depth, insert a new row of nodes with value val at depth depth and return the root. The root is at depth 1.
For every node cur at depth depth - 1, create two new nodes with value val. One becomes cur's new left child and the other its new right child. cur's original left subtree hangs under the new left node, as its left child, and its original right subtree hangs under the new right node, as its right child.
If depth == 1, create a new root with value val and make the whole original tree its left subtree.
Examples
Input: root = [5,2,7,1], val = 0, depth = 2 Output: [5,0,0,2,None,None,7,1]
Two 0-nodes go under 5. 2 becomes the left child of the left 0, and 7 the right child of the right 0.
Input: root = [3,4], val = 9, depth = 1 Output: [9,3,None,4]
At depth 1 a new root 9 takes the whole old tree as its left subtree.
Input: root = [4,2,6,3,1,5], val = 1, depth = 3 Output: [4,2,6,1,1,1,1,3,None,None,1,5]
Nodes 2 and 6 are at depth 2. Each gets two new 1-nodes; 3 and 5 move under the left ones and 1 under the right one of 2.
Constraints
- 1 <= number of nodes <= 10^4
- The depth of the tree is at most 10^4
- -100 <= Node.val <= 100
- -10^5 <= val <= 10^5
- 1 <= depth <= (depth of the tree) + 1
Approaches
- Baseline: recursive walk carrying the depth — time O(n), space O(h) for the call stack
Follow-up
Every node at depth depth - 1 is rewired the same way, so the only real work is reaching that level. The use cases undo the operation (remove a row) and add the new nodes under every leaf instead of at one depth.
Related problems
Start free on Cariara · Coding problems · System design studio
