Add One Row To Tree - Leetcode Solution

The problem statement can be found here: https://leetcode.com/problems/add-one-row-to-tree/

Problem Description:

Given the root of a binary tree, then value v and depth d, insert a row of nodes with value v at the given depth d.

The root node is at depth 1.

Example 1: Input: 4 /
2 6 / \ /
3 1 5 7

v = 1, d = 2

Output: 4 /
1 1 / \ /
2 6 5 7 /
3 1

Example 2: Input: 4 /
2
/ \
3 1

v = 1, d = 3

Output: 4 /
2 /
3 1 / 1

Approach:

• Create a recursive function that takes the node, level, the value to be inserted, and the target depth as arguments.

• Base case:

  • If the current level is one less than the target depth, we need to insert a new row of nodes at this level.
  • Create new nodes with the given value and set their left and right children to be the previous left and right children of the current node.

• Recursive case:

  • Recursively call the function on the left and right children of the current node if they exist, decrementing the level by one each time.

• Call the recursive function on the root node with the initial level being 1.

• Return the modified root node.

Solution:

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1){
            // create new root node with v as the value and set its left child as the previous root node
            TreeNode* newRoot = new TreeNode(v);
            newRoot->left = root;
            return newRoot;
        }
        addOneRowDFS(root, 1, v, d);
        return root;
    }
    
    void addOneRowDFS(TreeNode* node, int level, int v, int d){
        if(node == NULL){
            return;
        }
        if(level == d-1){
            // create new left node with v as the value and set its left and right children
            TreeNode* newLeft = new TreeNode(v);
            newLeft->left = node->left;
            node->left = newLeft;
            
            // create new right node with v as the value and set its left and right children
            TreeNode* newRight = new TreeNode(v);
            newRight->right = node->right;
            node->right = newRight;
        }
        else{
            addOneRowDFS(node->left, level+1, v, d);
            addOneRowDFS(node->right, level+1, v, d);
        }
    }
};

Time Complexity:

Since we are traversing all the nodes in the given tree, the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity:

The space complexity is O(h), where h is the height of the tree. This is because the recursive function call stack will have at most h elements.

1