Leetcode 623: Add One Row to Tree [Solution]

This question consists of simple problem with multiple ways to solve this. I like recursion so I decided to go with that approach. The question doesn't seem to have many edge cases so if you are getting correct answer for the example test cases and a little variation to them, you will get your submission approved easily.

Difficulty: Medium
Jump To:

• Problem Statement
• Explanation
• Solution
• Implementation

Problem Statement

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

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

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

1. The given d is in the range [1, maximum depth of the given tree + 1].
2. The given binary tree has at least one tree node.

Explanation

So the problem is quite simple, You are given a non-empty binary tree and a value v which needs to be inserted as a child at depth d for all non-empty parent nodes. The new node will be at both left and right edge of the parent. The child nodes/subtree of the parent need to be set as the child of the newly created node with the same direction left/right. This should be clear with the given examples.

Solution

We are going to do only the below things:

1. If depth=1 i.e. we need to add the value at root, then we just need to create a new node with value v and make the current root its left child and return the pointer to the new node.
2. We need to traverse the tree in both directions (left/right) till we reach the depth d-1. Let's say we are at the node parent, this is the node below which the new nodes need to be added.
3. Now we need to create a new node for the left subtree of parent so this new node's left pointer will point to the left subtree of parent and then we'll make parent's left pointer point to the new node. That's how we have added a node between the parent and left subtree.
4. Same needs to be done for the right subtree.

As we'll be going down to the tree, we can call it DFS(Depth First Search) based on recursion. So Time Complexity: of this solution may go to O(n) as we might need to add the nodes below the leaf. As recursion uses stack so the Space Complexity: can be O(n) in the worst case.

Implementation

C++ Code:

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        // If need to add the row on root
        if(d==1){
            // Just create a new node with value v 
            // and current root as left child
            TreeNode *ptr = new TreeNode(v, root, nullptr);
            return ptr;
        }

        // Traverse down to the parent node at depth d-1
        // to add row at depth d(>1)
        addRow(root, v, d-1);

        // Return same pointer root with modified tree
        return root;
    }

    // Function to traverse down to the depth d-1 and add row
    void addRow(TreeNode* parent, int v, int dep){
        // If node is NULL the do nothing
        if(!parent)
            return;

        // If we have reached depth d-1 i.e. dep=1
        if(dep==1){
            TreeNode *temp;

            // Store left ptr
            temp = parent->left; 
            // Replace left ptr with new node with value v
            parent->left = new TreeNode(v);
            // Set stored left pointer as new node's left ptr
            parent->left->left = temp;

            // Store right ptr
            temp = parent->right;
            // Replace right ptr with new node with value v
            parent->right = new TreeNode(v);
            // Set stored right pointer as new node's right ptr
            parent->right->right = temp;
        }
        // Else go deeper
        else{
            addRow(parent->left, v, dep-1);
            addRow(parent->right, v, dep-1);
        }
    }
};

Runnable C++ Code: