Construct Binary Tree from given Parent Array representation | C # program to construct a binary tree from parent array ; A binary tree 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 Code
using System ; public class Node { public int key ; public Node left , right ; public Node ( int key ) { this . key = key ; left = right = null ; } } class GFG { public Node root ; public virtual void createNode ( int [ ] parent , int i , Node [ ] created ) { if ( created [ i ] != null ) { return ; } created [ i ] = new Node ( i ) ; if ( parent [ i ] == - 1 ) { root = created [ i ] ; return ; } if ( created [ parent [ i ] ] == null ) { createNode ( parent , parent [ i ] , created ) ; } Node p = created [ parent [ i ] ] ; if ( p . left == null ) { p . left = created [ i ] ; } else { p . right = created [ i ] ; } } public virtual Node createTree ( int [ ] parent , int n ) { Node [ ] created = new Node [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { created [ i ] = null ; } for ( int i = 0 ; i < n ; i ++ ) { createNode ( parent , i , created ) ; } return root ; } public virtual void newLine ( ) { Console . WriteLine ( " " ) ; } public virtual void inorder ( Node node ) { if ( node != null ) { inorder ( node . left ) ; Console . Write ( node . key + " ▁ " ) ; inorder ( node . right ) ; } } public static void Main ( string [ ] args ) { GFG tree = new GFG ( ) ; int [ ] parent = new int [ ] { - 1 , 0 , 0 , 1 , 1 , 3 , 5 } ; int n = parent . Length ; Node node = tree . createTree ( parent , n ) ; Console . WriteLine ( " Inorder ▁ traversal ▁ of ▁ " + " constructed ▁ tree ▁ " ) ; tree . inorder ( node ) ; tree . newLine ( ) ; } }