Construct Tree from given Inorder and Preorder traversals | Java program to construct tree using inorder and preorder traversals ; A binary tree node has data , pointer to left child and a pointer to right child ; Store indexes of all items so that we we can quickly find later ; 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 ; This function mainly creates an unordered_map , then calls buildTree ( ) ; This funtcion is here just to test buildTree ( ) ; Driver code ; Let us test the built tree by printing Insorder traversal
import java . io . * ; import java . util . * ; class Node { char data ; Node left , right ; Node ( char item ) { data = item ; left = right = null ; } } class Tree { public static Node root ; static HashMap < Character , Integer > mp = new HashMap < > ( ) ; static int preIndex = 0 ; public static Node buildTree ( char [ ] in , char [ ] pre , int inStrt , int inEnd ) { if ( inStrt > inEnd ) { return null ; } char curr = pre [ preIndex ++ ] ; Node tNode ; tNode = new Node ( curr ) ; if ( inStrt == inEnd ) { return tNode ; } int inIndex = mp . get ( curr ) ; tNode . left = buildTree ( in , pre , inStrt , inIndex - 1 ) ; tNode . right = buildTree ( in , pre , inIndex + 1 , inEnd ) ; return tNode ; } public static Node buldTreeWrap ( char [ ] in , char [ ] pre , int len ) { for ( int i = 0 ; i < len ; i ++ ) { mp . put ( in [ i ] , i ) ; } return buildTree ( in , pre , 0 , len - 1 ) ; } static 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 ) { char [ ] in = { ' D ' , ' B ' , ' E ' , ' A ' , ' F ' , ' C ' } ; char [ ] pre = { ' A ' , ' B ' , ' D ' , ' E ' , ' C ' , ' F ' } ; int len = in . length ; Tree . root = buldTreeWrap ( in , pre , len ) ; System . out . println ( " Inorder ▁ traversal ▁ of ▁ the ▁ constructed ▁ tree ▁ is " ) ; printInorder ( root ) ; } }