Construct a Binary Tree from Postorder and Inorder | Java program for above approach ; Node class ; Constructor ; Tree building function ; Create Stack of type Node * ; Create HashSet of type Node * ; Initialise postIndex with n - 1 ; Initialise root with null ; Initialise node with NULL ; Run do - while loop ; Initialise node with new Node ( post [ p ] ) ; ; Check is root is equal to NULL ; If size of set is greater than 0 ; If st . peek ( ) is present in the set s ; If the stack is not empty and st . top ( ) . data is equal to in [ i ] ; Pop elements from stack ; If node not equal to NULL ; Return root ; For print preOrder Traversal ; Driver Code ; Function Call ; Function Call for preOrder
import java . io . * ; import java . util . * ; class GFG { static class Node { int data ; Node left , right ; Node ( int x ) { data = x ; left = right = null ; } } static Node buildTree ( int in [ ] , int post [ ] , int n ) { Stack < Node > st = new Stack < > ( ) ; HashSet < Node > s = new HashSet < > ( ) ; int postIndex = n - 1 ; Node root = null ; for ( int p = n - 1 , i = n - 1 ; p >= 0 { Node node = null ; do { node = new Node ( post [ p ] ) ; if ( root == null ) { root = node ; } if ( st . size ( ) > 0 ) { if ( s . contains ( st . peek ( ) ) ) { s . remove ( st . peek ( ) ) ; st . peek ( ) . left = node ; st . pop ( ) ; } else { st . peek ( ) . right = node ; } } st . push ( node ) ; } while ( post [ p -- ] != in [ i ] && p >= 0 ) ; node = null ; while ( st . size ( ) > 0 && i >= 0 && st . peek ( ) . data == in [ i ] ) { node = st . peek ( ) ; st . pop ( ) ; i -- ; } if ( node != null ) { s . add ( node ) ; st . push ( node ) ; } } return root ; } 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 ) ; } }