Build Binary Tree from given Parent array

Given an array A which represents a binary tree such that the parent-child relationship is defined by (A[i], i) for every index i in the array A, build binary tree out of it. The value of root node will be i if -1 is present at index i in the array. It may be assumed that the input provided to the program is valid.


 

For example, consider below array


parent[] = {-1, 0, 0, 1, 2, 2, 4, 4}
index:       0, 1, 2, 3, 4, 5, 6, 7

 
– Root is represented by value -1 in the parent array which is present at index 0
– 0 is present at index 1 and 2 which represents left and right child of root.
– 1 is present at index 3 which represents left or right child of 1
– 2 is present at index 4 and 5 which represents left and right child of it.
– 4 is present at index 6 and 7 which represents left and right child of it.

 
Build Binary Tree from Parent Array
 

 
The solution is very simple and effective. We create n new tree nodes each having value from 0 to n-1 where n is the size of the array and store them in a map or array for quick lookup. Then we traverse the given parent array and build the tree by setting parent-child relationship defined by (A[i], i) for every index i in the array A. As several binary trees can be constructed from one input, below solution would construct any one of them. The solution will always set left child for a node before setting its right child.

C++

Download   Run Complete Code

 
The time complexity of above solution is O(n) (assuming constant time operations for std::unordered_map) and auxiliary space used by the program is O(1).

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Tejaswi
Guest

how do we find no of internal nodes if we do level order traversal for this code