Last Updated: 11 Nov, 2020
Binary Tree from Parent Array
Easy
Asked in companies
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:-
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:-
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:-
And for {1, -1}, the accepted tree will be,
Instead of
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 :
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.
Approaches
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.
- Find out the 'ROOT' node by searching for ‘-1’ in the given 'PARENT' array.
- 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'[] ):
- Traverse the whole array and find out the 'ROOT' node i.e. store 'INDEX' when 'PARENT'['INDEX'] = -1.
- 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'.
- Let us walk through the approach along with an example where 'PARENT'={1, 5, 5, 2, 2, -1, 3}:-
- First off, create a list that stores tree nodes. Note that tree node values can be 0 to N-1, thus make tree nodes for all these values and store them in a list say NODE.
For the above example, the list will be:-
- Create a root node, say root which will be updated by the root of the binary tree we are forming.
Now, we traverse the 'PARENT' array from start to end and perform the following:- - If 'PARENT'['INDEX'] = -1: this means that we have got the value of root node which is index. Remember, we have already created a node of the value index which is stored at 'NODE'['INDEX']. Thus, we update root with 'NODE'['INDEX'].
Otherwise, we need to create a tree possible from 'PARENT'['INDEX'], as 'PARENT'['INDEX'] is the 'PARENT' of index and we have already made nodes for the value 'PARENT'['INDEX'] as well as the index.
Firstly, we will make left child:
'NODE'['PARENT'['INDEX']] -> left = 'NODE'['INDEX']
If the left child is not NULL i.e. we already have left the child for a particular 'PARENT'['INDEX'], we create a right child:
'NODE'['PARENT'['INDEX']] -> right = 'NODE'['INDEX'] - Walking through the above-told example:
'PARENT' = {1, 5, 5, 2, 2, -1, 3}
For index = 0, as, 'PARENT'['INDEX'] != -1, we create tree as:
'NODE'['PARENT'[0]] -> left = 'NODE'[0]
'NODE'[1] -> left = 'NODE'[0]
- For index = 1, as, 'PARENT'['INDEX'] != -1, we create tree as:
'NODE'['PARENT'[1]] -> left = 'NODE'[1]
'NODE'[5] -> left = 'NODE'[1]
For index = 2, as, 'PARENT'['INDEX'] != -1, we create tree as:
'NODE'['PARENT'[2]] -> left = 'NODE'[2]
'NODE'[5] -> left = 'NODE'[2], we see that 'NODE'[5] -> left is not NULL, thus,
We update it with the right child:
'NODE'[5] -> right = 'NODE'[2]
- Similarly, for index 3 and 4, the 'NODE' list becomes:
'NODE'[2] -> left = 'NODE'[3]
'NODE'[2] -> right = 'NODE'[4]
- In the case of 'INDEX' = 5, we incur -1, thus, we make 'NODE'[5] as the root.
Finally, the 'NODE' list will be:
- Now, return the root i.e. 'NODE'[5]
- Note: The above array representation is only to show the representation of the node at the ith index of the 'NODE' array and its subtree. In actual, each index of the 'NODE' array will only store the reference to a single node, not the complete tree separately.