text: Construct Tree from given Inorder and Preorder traversals | 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 program to test above functions ; Let us test the built tree by printing Insorder traversal
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { char data ; struct node * left ; struct node * right ; } ; int search ( char arr [ ] , int strt , int end , char value ) ; struct node * newNode ( char data ) ; struct node * buildTree ( char in [ ] , char pre [ ] , int inStrt , int inEnd ) { static int preIndex = 0 ; if ( inStrt > inEnd ) return NULL ; struct 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 ; } } struct node * newNode ( char data ) { struct node * node = ( struct node * ) malloc ( sizeof ( struct node ) ) ; node -> data = data ; node -> left = NULL ; node -> right = NULL ; return ( node ) ; } void printInorder ( struct node * node ) { if ( node == NULL ) return ; printInorder ( node -> left ) ; printf ( " % c ▁ " , 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 ] ) ; struct node * root = buildTree ( in , pre , 0 , len - 1 ) ; printf ( " Inorder ▁ traversal ▁ of ▁ the ▁ constructed ▁ tree ▁ is ▁ STRNEWLINE " ) ; printInorder ( root ) ; getchar ( ) ; }