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).

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
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