Binary Tree from Parent Array

Posted: 11 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Given an array parent which represents a binary tree such that parent-child relationship is defined by ('PARENT'[i], 'i') which means that parent of i is 'PARENT'[i]. The value of the root node will be i if -1 is present at 'PARENT'[i].

For example:

For the parent array {1, -1, 1}, the tree will be:- 

1

As, parent of 0 is 'PARENT'[0] i.e. 1.
1 is the root as 'PARENT'[1] = -1.
Parent of 2 is 'PARENT'[2] i.e. 1.

Similarly for the parent array { 1, 2, -1}, the tree will be:-

2

Your task is to create the Binary tree from the given parent array.

Note:

From the parent array, multiple binary trees may be possible. You have to create a binary tree in such a way that these conditions satisfy:-

If the node has a left child as well as a right child, make sure the left child is smaller than the right child. 

If the node has only one child, make sure it has an only left child. 

For {1, -1, 1}, the accepted tree will be:- 

3

And for {1, -1}, the accepted tree will be, 

4

Instead of 

5

Input format:
The first line of input contains an integer 'T' denoting the number of queries or test cases. 

The first line of every test case contains an integer 'N' denoting the size of the parent array. 

The second line of every test case contains 'N' single space-separated integers, representing the elements of the parent array.
Output format:
For each test case, print the level order of the Binary tree in a separate line. 

For example, the level order output for the tree depicted in the below image would be :

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).
Note :
The above format was just to provide clarity on how the output is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'T' <= 100
1 <= 'N' <= 3000

Where 'T' is the number of test cases and 'N' denotes the number of nodes in the tree.

Time limit: 1 sec.
Approach 1

The idea here is to repeatedly find out the children of a particular node, attach them with their 'PARENT' node and work on the child nodes separately.

  • This can be achieved by:-
    • Find out the 'ROOT' node by searching for ‘-1’ in the given 'PARENT' array.
      Pass this 'ROOT' node as well as the 'PARENT' array into a helper function.
      The helper function returns us the final 'ROOT' of the binary tree by doing the following things:-
    • If the 'ROOT' is 'NULL', i.e. we are given the 'PARENT' array of a 'NULL' tree, returns 'NULL'.
      Otherwise, traverses the 'PARENT' array and finds out the children of the current 'ROOT'. Let us store 'LEFT' child in 'FIRST' and 'RIGHT' child in Second.
      Assigns 'FIRST' to the 'LEFT' child of 'ROOT' and recursively calls for the creation of subtree which has 'FIRST' as its 'ROOT'.
      Assigns Second to the 'RIGHT' child of 'ROOT' and recursively calls for the creation of subtree which has Second as its 'ROOT'.
      Return the 'ROOT' fetched from the helper function.
  • Algorithm:
  • Node 'CREATETREE'('PARENT'[]):
    • Traverse the whole array and find out the 'ROOT' node i.e. store 'INDEX' when 'PARENT'['INDEX'] = -1.
      Create a new 'ROOT' node with value 'INDEX'.
      Call 'CREATETREE'Helper('ROOT', 'PARENT') and store it in a Node say ans.
      Return ans.
    • Node* 'CREATETREEHELPER'( 'ROOT', List 'PARENT'[] ):
  • If the 'ROOT' is 'NULL', return 'NULL'.
     
  • Create Tree nodes that say 'FIRST' and second.
    Search for 'LEFT' and 'RIGHT' child i.e if: 'PARENT'['INDEX'] == 'ROOT'->data, 
     
  • For 'FIRST' time, 'FIRST' = Node('INDEX') 
     
  • For second time, second = Node('INDEX'). 
     
  • 'ROOT'->'LEFT' = 'CREATETREEHELPER'('FIRST', 'PARENT')
     
  • This creates the 'LEFT' subtree recursively.
     
  • 'ROOT'->'RIGHT' = 'CREATETREEHELPER'(second, 'PARENT')
     
  • This creates the 'RIGHT' subtree recursively.
     
  • Return 'ROOT'.
Try Problem