Construct Full Binary Tree from given preorder and postorder traversals | Java 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 program to test above functions
public class fullbinarytreepostpre { static int preindex ; static class node { int data ; node left , right ; public node ( int data ) { this . data = data ; } } 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 ; } static node constructTree ( int pre [ ] , int post [ ] , int size ) { preindex = 0 ; return constructTreeUtil ( pre , post , 0 , size - 1 , size ) ; } static void printInorder ( node root ) { if ( root == null ) return ; printInorder ( root . left ) ; System . out . print ( root . data + " ▁ " ) ; printInorder ( root . right ) ; } public static void main ( String [ ] args ) { int pre [ ] = { 1 , 2 , 4 , 8 , 9 , 5 , 3 , 6 , 7 } ; int post [ ] = { 8 , 9 , 4 , 5 , 2 , 6 , 7 , 3 , 1 } ; int size = pre . length ; node root = constructTree ( pre , post , size ) ; System . out . println ( " Inorder ▁ traversal ▁ of ▁ the ▁ constructed ▁ tree : " ) ; printInorder ( root ) ; } }