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 depth. The root node is at depth 1. If depth == 1, create a new root with value val, and the original tree becomes the left subtree of the new root.
Key Insights
- If the depth is 1, we simply create a new root node with the given value and attach the original tree as its left child.
- For depths greater than 1, we need to traverse the tree to the level just above the target depth, creating new nodes with the specified value to act as the new children for each node at that level.
- The original children of the nodes at depth - 1 become the children of the new nodes.
Space and Time Complexity
Time Complexity: O(n), where n is the number of nodes in the tree, as we may need to visit each node. Space Complexity: O(h), where h is the height of the tree, due to the recursive stack space in the depth-first search approach.
Solution
To solve this problem, we utilize a breadth-first search (BFS) or depth-first search (DFS) approach to navigate the tree. We keep track of the current depth as we traverse. When we reach the depth just above the target, we insert new nodes with the specified value as children of the current nodes, adjusting the original children accordingly.