Construct a Binary Tree from Postorder and Inorder | C # program to construct a tree using inorder and postorder traversals ; A binary tree node has data , pointer to left child and a pointer to right child ; Class Index created to implement pass by reference of Index ; Recursive function to construct binary of size n from Inorder traversal in [ ] and Postrder traversal post [ ] . Initial values of inStrt and inEnd should be 0 and n - 1. The function doesn 't do any error checking for cases where inorder and postorder do not form a tree  ; Base case ; Pick current node from Postrder traversal using postIndex and decrement postIndex ; If this node has no children then return ; Else find the index of this node in Inorder traversal ; Using index in Inorder traversal , construct left and right subtress ; This function mainly initializes index of root and calls buildUtil ( ) ; Function to find index of value in arr [ start ... end ] . The function assumes that value is postsent in in [ ] ; This funtcion is here just to test ; Driver Code
using System ; public class Node { public int data ; public Node left , right ; public Node ( int data ) { this . data = data ; left = right = null ; } } public class Index { public int index ; } class GFG { public virtual Node buildUtil ( int [ ] @in , int [ ] post , int inStrt , int inEnd , Index pIndex ) { if ( inStrt > inEnd ) { return null ; } Node node = new Node ( post [ pIndex . index ] ) ; ( pIndex . index ) -- ; if ( inStrt == inEnd ) { return node ; } int iIndex = search ( @in , inStrt , inEnd , node . data ) ; node . right = buildUtil ( @in , post , iIndex + 1 , inEnd , pIndex ) ; node . left = buildUtil ( @in , post , inStrt , iIndex - 1 , pIndex ) ; return node ; } public virtual Node buildTree ( int [ ] @in , int [ ] post , int n ) { Index pIndex = new Index ( ) ; pIndex . index = n - 1 ; return buildUtil ( @in , post , 0 , n - 1 , pIndex ) ; } public virtual int search ( int [ ] arr , int strt , int end , int value ) { int i ; for ( i = strt ; i <= end ; i ++ ) { if ( arr [ i ] == value ) { break ; } } return i ; } public virtual void preOrder ( Node node ) { if ( node == null ) { return ; } Console . Write ( node . data + " ▁ " ) ; preOrder ( node . left ) ; preOrder ( node . right ) ; } public static void Main ( string [ ] args ) { GFG tree = new GFG ( ) ; int [ ] @in = new int [ ] { 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 } ; int [ ] post = new int [ ] { 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 } ; int n = @in . Length ; Node root = tree . buildTree ( @in , post , n ) ; Console . WriteLine ( " Preorder ▁ of ▁ the ▁ constructed ▁ tree ▁ : ▁ " ) ; tree . preOrder ( root ) ; } }