Construct a Binary Tree from Postorder and Inorder | C # 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
using System ; using System . Collections . Generic ; class GFG { public class Node { public int data ; public Node left , right ; public Node ( int x ) { data = x ; left = right = null ; } } static Node buildTree ( int [ ] init , int [ ] post , int n ) { Stack < Node > st = new Stack < Node > ( ) ; HashSet < Node > s = new HashSet < Node > ( ) ; 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 . Count > 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 -- ] != init [ i ] && p >= 0 ) ; node = null ; while ( st . Count > 0 && i >= 0 && st . Peek ( ) . data == init [ 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 ; Console . Write ( node . data + " ▁ " ) ; preOrder ( node . left ) ; preOrder ( node . right ) ; } public static void Main ( String [ ] args ) { int [ ] init = { 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 } ; int [ ] post = { 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 } ; int n = init . Length ; Node root = buildTree ( init , post , n ) ; Console . Write ( " Preorder ▁ of ▁ the ▁ constructed ▁ tree ▁ : ▁ STRNEWLINE " ) ; preOrder ( root ) ; } }