Insert a new row of nodes with a given value at a specified depth in a binary tree.
Problem
You are given the root of a binary tree, an integer value val, and an integer depth depth.
Add a new row of nodes with value val at the given depth.
- If
depth = 1, create a new root node with valueval. - Otherwise, for every node that was originally at depth
depth - 1, insert two new nodes below it:- the new left child gets the original left subtree as its left child
- the new right child gets the original right subtree as its right child
All other existing structure should remain unchanged.
Goal
Return the root of the modified tree.
Input Format
- A binary tree root
- An integer
val - An integer
depth
Output Format
- The root of the updated binary tree
Constraints
1 <= depth <= $10^{4}$is typical for this kind of tree problem- Node values may be any integer
- The tree may be empty
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]
Explanation
A new row of value 1 is inserted at depth 2. The original children of the root are reattached beneath the new nodes.
Example 2
Input
root = [4,2,null,3,1], val = 1, depth = 3
Output
[4,2,null,1,1,null,null,3,null,null,1]
Explanation
Nodes are inserted below every node at depth 2, and the old subtrees are preserved under the newly created nodes.
Show 1 more example
Example 3
Input
root = [], val = 7, depth = 1
Output
[7]
Explanation
When the tree is empty and depth is 1, the result is a single new root node.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.