Construct a Binary Tree from Postorder and Inorder | Java program to contree using inorder and postorder traversals ; A binary tree node has data , pointer to left child and a pointer to right child ; Recursive function to conbinary of size n from Inorder traversal in [ ] and Postorder 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 Postorder 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 , con left and right subtress ; This function mainly creates an unordered_map , then calls buildTreeUtil ( ) ; Store indexes of all items so that we we can quickly find later ; Index in postorder ; Helper function that allocates a new node ; This funtcion is here just to test ; Driver code
import java . util . * ; class GFG { static class Node { int data ; Node left , right ; } ; static Node buildUtil ( int in [ ] , int post [ ] , int inStrt , int inEnd ) { if ( inStrt > inEnd ) return null ; int curr = post [ index ] ; Node node = newNode ( curr ) ; ( index ) -- ; if ( inStrt == inEnd ) return node ; int iIndex = mp . get ( curr ) ; node . right = buildUtil ( in , post , iIndex + 1 , inEnd ) ; node . left = buildUtil ( in , post , inStrt , iIndex - 1 ) ; return node ; } static HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; static int index ; static Node buildTree ( int in [ ] , int post [ ] , int len ) { for ( int i = 0 ; i < len ; i ++ ) mp . put ( in [ i ] , i ) ; index = len - 1 ; return buildUtil ( in , post , 0 , len - 1 ) ; } static Node newNode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = node . right = null ; return ( node ) ; } static void preOrder ( Node node ) { if ( node == null ) return ; System . out . printf ( " % d ▁ " , node . data ) ; preOrder ( node . left ) ; preOrder ( node . right ) ; } public static void main ( String [ ] args ) { int in [ ] = { 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 } ; int post [ ] = { 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 } ; int n = in . length ; Node root = buildTree ( in , post , n ) ; System . out . print ( "Preorder of the constructed tree : NEW_LINE"); preOrder ( root ) ; } }