623. Add One Row to Tree


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 range [1, maximum depth of the given tree + 1].
  2. The given binary tree has at least one tree node.


Solution

Approach #1 Using Recursion(DFS) [Accepted]

If the given depth happens to be equal to 1, we can directly put the whole current tree as a left child of the newly added node. Otherwise, we need to put the new node at appropriate levels.

To do so, we make use of a recursive function insert(val,node,depth,n). Here, refers to the value of the new node to be inserted, refers to the depth of the node currently considered, refers to the node calling the current function for its child subtrees and refers to the height at which the new node needs to be inserted.

For inserting the new node at appropriate level, we can start by making a call to insert with the root node and 1 as the current level. Inside every such call, we check if we've reached one level prior to the level where the new node needs to be inserted.

From this level, we can store the roots of the left and right subtrees of the current node temporarily, and insert the new node as the new left and right subchild of the current node, with the temporarily stored left and right subtrees as the left and right subtrees of the newly inserted left or right subchildren appropriately.

But, if we haven't reached the destined level, we keep on continuing the recursive calling process with the left and right children of the current node respectively. At every such call, we also incrmenet the depth of the current level to reflect the depth change appropriately.

The animation below illustrates the process:

!?!../Documents/623_Add_One_Row_Recursion_New.json:1000,563!?!

Complexity Analysis

  • Time complexity : . A total of nodes of the given tree will be considered.

  • Space complexity : . The depth of the recursion tree can go upto in the worst case(skewed tree).

Approach #2 Using stack(DFS) [Accepted]

Algorithm

We can do the same task as discussed in the last approach by making use of a as well. But, we need to make use of a new data structure, here, to keep a track of the depth of the current node along with its value.

We start by pushing the root onto the . Then, at every step we do as follows:

  • Pop an element from the .

  • For every Node popped, check if its depth corresponds to one prior to the depth at which the new node needs to be inserted.

  • If yes, insert the new nodes appropriately as in the last approach.

  • If no, we push both the left and the right child Node(value+depth) of the current node onto the .

  • Continue the popping and pushing process till the becomes empty.

Look at the animation below for a better understanding.

!?!../Documents/623_Add_One_Row_Stack_new.json:1000,563!?!

Complexity Analysis

  • Time complexity : . A total of nodes of the given tree will be considered.

  • Space complexity : . The depth of the can go upto in the worst case(skewed tree).

Approach #3 Using queue(BFS) [Accepted]

Algorithm

The idea of traversal in the last approach is similar to Depth First Search. In that case, we need to traverse through all the nodes of the given tree in the order of branches. Firstly we explored one branch to as much depth as possible and then continued with the other ones.

If, instead, we go for Breadth First Search, along with keeping track of the depth of the nodes being considered at any moment during the Breadth First Search, we can stop the search process as soon as all the nodes at the depth have been considered once.

To implement this BFS, we make use of a . We start off by pushing the root node of the given tree at the back of the and with the depth of the current level set as 1. Then, at every step, we do the following:

  • Remove an element from the front of the and add all its children to the back of another temporary queue, .

  • Keep on adding the elements to the back of the till becomes empty. (Once becomes empty, it indicates that all the nodes at the current level have been considered and now contains all the nodes lying at the next level).

  • Reinitialize with its value as . Update the current value of the to reflect the level of nodes currently being considered.

  • Repeat the process till we reach the depth .

  • On hitting this depth level(), add the new nodes appropriately to all the nodes in the currently, as done in the previous approaches.

The following animation illustrates the process.

!?!../Documents/623_Add_One_Row_queue_new.json:1000,563!?!

Complexity Analysis

  • Time complexity : . A total of nodes of the given tree will be considered in the worst case.

  • Space complexity : . The size of the or queue can grow upto only. Here, refers to the number of maximum number of nodes at any level in the given tree.

Analysis written by: @vinod23

Submit Solution