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 ; Prototypes for utility functions ; 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 [ ] ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; 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 code ; Let us test the built tree by printing Insorder traversal
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : char data ; node * left ; node * right ; } ; int search ( char arr [ ] , int strt , int end , char value ) ; node * newNode ( char data ) ; node * buildTree ( char in [ ] , char pre [ ] , int inStrt , int inEnd ) { static int preIndex = 0 ; if ( inStrt > inEnd ) return NULL ; node * tNode = newNode ( 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 ; } } node * newNode ( char data ) { node * Node = new node ( ) ; Node -> data = data ; Node -> left = NULL ; Node -> right = NULL ; return ( Node ) ; } void printInorder ( node * node ) { if ( node == NULL ) return ; printInorder ( node -> left ) ; cout << node -> data << " ▁ " ; printInorder ( node -> right ) ; } int main ( ) { char in [ ] = { ' D ' , ' B ' , ' E ' , ' A ' , ' F ' , ' C ' } ; char pre [ ] = { ' A ' , ' B ' , ' D ' , ' E ' , ' C ' , ' F ' } ; int len = sizeof ( in ) / sizeof ( in [ 0 ] ) ; node * root = buildTree ( in , pre , 0 , len - 1 ) ; cout << " Inorder ▁ traversal ▁ of ▁ the ▁ constructed ▁ tree ▁ is ▁ STRNEWLINE " ; printInorder ( root ) ; }