Construct Tree from given Inorder and Preorder traversals | A binary tree node has data , pointer to left child and a pointer to right child ; Recursive function to construct binary of size len from Inorder traversal in [ ] and Preorder traversal pre [ ] . Initial values of inStrt and inEnd should be 0 and len - 1. The function doesn 't do any error checking for cases where  inorder and preorder do not form a tree  ; Pick current node from Preorder traversal using preIndex and increment preIndex ; 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 ; Function to find index of value in arr [ start ... end ] The function assumes that value is present in in [ ] ; This funtcion is here just to test buildTree ( ) ; first recur on left child ; then print the data of node ; now recur on right child ; driver program to test above functions ; building the tree by printing inorder traversal
class Node { char data ; Node left , right ; Node ( char item ) { data = item ; left = right = null ; } } class BinaryTree { Node root ; static int preIndex = 0 ; Node buildTree ( char in [ ] , char pre [ ] , int inStrt , int inEnd ) { if ( inStrt > inEnd ) return null ; Node tNode = new Node ( pre [ preIndex ++ ] ) ; if ( inStrt == inEnd ) return tNode ; int inIndex = search ( in , inStrt , inEnd , tNode . data ) ; tNode . left = buildTree ( in , pre , inStrt , inIndex - 1 ) ; tNode . right = buildTree ( in , pre , inIndex + 1 , inEnd ) ; return tNode ; } int search ( char arr [ ] , int strt , int end , char value ) { int i ; for ( i = strt ; i <= end ; i ++ ) { if ( arr [ i ] == value ) return i ; } return i ; } void printInorder ( Node node ) { if ( node == null ) return ; printInorder ( node . left ) ; System . out . print ( node . data + " ▁ " ) ; printInorder ( node . right ) ; } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; char in [ ] = new char [ ] { ' D ' , ' B ' , ' E ' , ' A ' , ' F ' , ' C ' } ; char pre [ ] = new char [ ] { ' A ' , ' B ' , ' D ' , ' E ' , ' C ' , ' F ' } ; int len = in . length ; Node root = tree . buildTree ( in , pre , 0 , len - 1 ) ; System . out . println ( " Inorder ▁ traversal ▁ of ▁ constructed ▁ tree ▁ is ▁ : ▁ " ) ; tree . printInorder ( root ) ; } }