Construct Binary Tree from Parent Array

Construct Binary Tree from Parent Array

Given an array that represents a Tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root.

Solution:

  • Create an extra array
  • Iterate twice parent array
    • First time only create node
    • Second time update parent-child association link
Algorithm:
  1. Create an extra array to hold binary tree node
  2. Iterate from given array from index 0 to n-1
    1. create node with index and put that in extra array
  3. Iterate from given array from index 0 to n-1
    1. Get node for index and value from extra array
    2. Add parent child association between these nodes

Latest Source Code:
Github: BinaryTreeFromParentArray.java


Output:

Array is : -1 0 0 1 1 3 5 Print created tree
               0                               
              / \               
             /   \              
            /     \             
           /       \            
          /         \           
         /           \          
        /             \         
       /               \        
       1               2               
      / \                       
     /   \                      
    /     \                     
   /       \                    
   3       4                       
  /                             
 /                              
 5                               
/                               
6                               
                                                                
---------------------------------------------------------------
Array is : 1 5 5 2 2 -1 3 Print created tree
       5               
      / \       
     /   \      
    /     \     
   /       \    
   1       2       
  /       / \   
 /       /   \  
 0       3   4   
        /       
        6       
               
Author: Hrishikesh Mishra