Construct Full Binary Tree from given preorder and postorder traversals | C # program for construction of full binary tree ; A binary tree node has data , pointer to left child and a pointer to right child ; A recursive function to construct Full from pre [ ] and post [ ] . preIndex is used to keep track of index in pre [ ] . l is low index and h is high index for the current subarray in post [ ] ; Base case ; The first node in preorder traversal is root . So take the node at preIndex from preorder and make it root , and increment preIndex ; If the current subarry has only one element , no need to recur or preIndex > size after incrementing ; Search the next element of pre [ ] in post [ ] ; Use the index of element found in postorder to divide postorder array in two parts . Left subtree and right subtree ; The main function to construct Full Binary Tree from given preorder and postorder traversals . This function mainly uses constructTreeUtil ( ) ; A utility function to print inorder traversal of a Binary Tree ; Driver Code
using System ; class GFG { public static int preindex ; public class node { public int data ; public node left , right ; public node ( int data ) { this . data = data ; } } public static node constructTreeUtil ( int [ ] pre , int [ ] post , int l , int h , int size ) { if ( preindex >= size l > h ) { return null ; } node root = new node ( pre [ preindex ] ) ; preindex ++ ; if ( l == h preindex >= size ) { return root ; } int i ; for ( i = l ; i <= h ; i ++ ) { if ( post [ i ] == pre [ preindex ] ) { break ; } } if ( i <= h ) { root . left = constructTreeUtil ( pre , post , l , i , size ) ; root . right = constructTreeUtil ( pre , post , i + 1 , h , size ) ; } return root ; } public static node constructTree ( int [ ] pre , int [ ] post , int size ) { preindex = 0 ; return constructTreeUtil ( pre , post , 0 , size - 1 , size ) ; } public static void printInorder ( node root ) { if ( root == null ) { return ; } printInorder ( root . left ) ; Console . Write ( root . data + " ▁ " ) ; printInorder ( root . right ) ; } public static void Main ( string [ ] args ) { int [ ] pre = new int [ ] { 1 , 2 , 4 , 8 , 9 , 5 , 3 , 6 , 7 } ; int [ ] post = new int [ ] { 8 , 9 , 4 , 5 , 2 , 6 , 7 , 3 , 1 } ; int size = pre . Length ; node root = constructTree ( pre , post , size ) ; Console . WriteLine ( " Inorder ▁ traversal ▁ of ▁ " + " the ▁ constructed ▁ tree : " ) ; printInorder ( root ) ; } }