Tree: Add One Row to Tree

Day 17:

Problem Statement: 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:

root node: depth 1. The adding rule is:

• Given : currDepth == 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 and cur's original right subtree should be the right subtree of the new right subtree root.
• If depth == 1, 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.

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
        

Approach : DFS

1. If depth =1, then create new RootNode and assign original root as left child of new root.
2. Maintain curr variable,to keep track of currentDepth of node.
3. Now recursively call left and right subtree with increasing current ,till curr is equal to depth -1.
4. If curr ==depth-1 , then create two tempNode (leftTemp and rightTemp) and store current left and right respectively.
5. Update currLeft and currRight with new val.
6. Assign tempNode to left of currentleft and right of currentRight.

Code:

• Time Complexity: The time complexity of this approach is O(N), where N is the number of nodes in the binary tree, as we need to traverse the entire tree to add the new row.
• Space Complexity: The space complexity is also O(N), where N is the number of nodes, due to the recursive calls and the stack space used during traversal.