Construct Binary Tree from given Parent Array representation | C ++ program to construct a Binary Tree from parent array ; A tree node ; Utility function to create new Node ; Creates a node with key as ' i ' . If i is root , then it changes root . If parent of i is not created , then it creates parent first ; If this node is already created ; Create a new node and set created [ i ] ; If ' i ' is root , change root pointer and return ; If parent is not created , then create parent first ; Find parent pointer ; If this is first child of parent ; If second child ; Creates tree from parent [ 0. . n - 1 ] and returns root of the created tree ; Create an array created [ ] to keep track of created nodes , initialize all entries as NULL ; For adding new line in a program ; Utility function to do inorder traversal ; Driver method
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } void createNode ( int parent [ ] , int i , Node * created [ ] , Node * * root ) { if ( created [ i ] != NULL ) return ; created [ i ] = newNode ( i ) ; if ( parent [ i ] == -1 ) { * root = created [ i ] ; return ; } if ( created [ parent [ i ] ] == NULL ) createNode ( parent , parent [ i ] , created , root ) ; Node * p = created [ parent [ i ] ] ; if ( p -> left == NULL ) p -> left = created [ i ] ; else p -> right = created [ i ] ; } Node * createTree ( int parent [ ] , int n ) { Node * created [ n ] ; for ( int i = 0 ; i < n ; i ++ ) created [ i ] = NULL ; Node * root = NULL ; for ( int i = 0 ; i < n ; i ++ ) createNode ( parent , i , created , & root ) ; return root ; } inline void newLine ( ) { cout << " STRNEWLINE " ; } void inorder ( Node * root ) { if ( root != NULL ) { inorder ( root -> left ) ; cout << root -> key << " ▁ " ; inorder ( root -> right ) ; } } int main ( ) { int parent [ ] = { -1 , 0 , 0 , 1 , 1 , 3 , 5 } ; int n = sizeof parent / sizeof parent [ 0 ] ; Node * root = createTree ( parent , n ) ; cout << " Inorder ▁ Traversal ▁ of ▁ constructed ▁ tree STRNEWLINE " ; inorder ( root ) ; newLine ( ) ; }