Construct Tree from given Inorder and Preorder traversals | C # 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
using System ; using System . Collections . Generic ; public class Node { public char data ; public Node left , right ; public Node ( char d ) { data = d ; left = right = null ; } } public class Tree { public static Node root ; static Dictionary < char , int > mp = new Dictionary < char , int > ( ) ; static int preIndex = 0 ; 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 [ 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 . Add ( In [ i ] , i ) ; } return buildTree ( In , pre , 0 , len - 1 ) ; } static void printInorder ( Node node ) { if ( node == null ) { return ; } printInorder ( node . left ) ; Console . Write ( node . data + " ▁ " ) ; printInorder ( node . right ) ; } static public void Main ( ) { 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 ) ; Console . WriteLine ( " Inorder ▁ traversal ▁ of ▁ the ▁ constructed ▁ tree ▁ is " ) ; printInorder ( Tree . root ) ; } }