Add One Row to Tree
MedPrompt
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:
- Given the integer
depth, for each not null tree nodecurat the depthdepth - 1, create two tree nodes with valuevalascur'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 == 1that means there is no depthdepth - 1at all, then create a tree node with valuevalas 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:
- The number of nodes in the tree is in the range
[1, 104]. - The depth of the tree is in the range
[1, 104]. -100 <= Node.val <= 100-105 <= val <= 1051 <= depth <= the depth of tree + 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses recursion to traverse the tree. A helper function is used which keeps track of the current depth. When it reaches the target depth (depth - 1), it performs the insertion of the new row.
Algorithm
- Handle the edge case where
depthis 1. Create a new root with the givenval, make the original tree its left child, and return the new root. - If
depthis not 1, call a recursive helper functioninsert(root, val, depth, 1). - The
insertfunction takes the current node, value, target depth, and current depth. - If the current node is
null, return. - If
currentDepth == depth - 1, this is the parent level. Modify its children:- Store the original left and right children.
- Create new nodes with
valand set them as the new left and right children. - Attach the original left subtree to the new left node's left child.
- Attach the original right subtree to the new right node's right child.
- Return to stop traversing deeper.
- Otherwise, recursively call
insertfor the left and right children withcurrentDepth + 1.
Walkthrough
This approach traverses the tree using recursion. A helper function, insert, is defined which takes the current node, the value to insert, the target depth, and the current depth as arguments. The base case for the recursion is when the current node is null. The main logic is executed when the currentDepth reaches depth - 1. At this point, the new row is inserted by creating two new nodes and rewiring the left and right pointers of the current node. The original subtrees are then attached to the newly created nodes. If the currentDepth is less than depth - 1, the function calls itself on the left and right children, incrementing the currentDepth. The special case of depth = 1 is handled separately in the main function by creating a new root and attaching the original tree as its left child.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode addOneRow(TreeNode root, int val, int depth) { if (depth == 1) { TreeNode newRoot = new TreeNode(val); newRoot.left = root; return newRoot; } insert(root, val, depth, 1); return root; } private void insert(TreeNode node, int val, int depth, int currentDepth) { if (node == null) { return; } if (currentDepth == depth - 1) { TreeNode tempLeft = node.left; TreeNode tempRight = node.right; node.left = new TreeNode(val); node.right = new TreeNode(val); node.left.left = tempLeft; node.right.right = tempRight; return; // Pruning the traversal } insert(node.left, val, depth, currentDepth + 1); insert(node.right, val, depth, currentDepth + 1); }}Complexity
Time
O(N), where N is the number of nodes in the tree. In the worst case, we might have to visit all nodes to find the nodes at `depth - 1`.
Space
O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be O(N), where N is the number of nodes.
Trade-offs
Pros
Conceptually simple and often leads to concise code for tree traversals.
Can be more space-efficient than BFS for wide, shallow trees.
Cons
Can lead to a
StackOverflowErrorfor extremely deep trees.May be less space-efficient than BFS for skewed trees where the height H is close to the number of nodes N.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int val ; private int depth ; public TreeNode addOneRow ( TreeNode root , int val , int depth ) { if ( depth == 1 ) { return new TreeNode ( val , root , null ); } this . val = val ; this . depth = depth ; dfs ( root , 1 ); return root ; } private void dfs ( TreeNode root , int d ) { if ( root == null ) { return ; } if ( d == depth - 1 ) { TreeNode l = new TreeNode ( val , root . left , null ); TreeNode r = new TreeNode ( val , null , root . right ); root . left = l ; root . right = r ; return ; } dfs ( root . left , d + 1 ); dfs ( root . right , d + 1 ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.