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.


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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

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