text: Construct Special Binary Tree from given Inorder traversal | program to construct tree from inorder traversal ; A binary tree node has data , pointer to left child and a pointer to right child ; Prototypes of a utility function to get the maximum value in inorder [ start . . end ] ; Recursive function to construct binary of size len from Inorder traversal inorder [ ] . Initial values of start and end should be 0 and len - 1. ; Find index of the maximum element from Binary Tree ; Pick the maximum value and make it root ; If this is the only element in inorder [ start . . end ] , then return it ; Using index in Inorder traversal , construct left and right subtress ; Function to find index of the maximum value in arr [ start ... end ] ; 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 ; Assume that inorder traversal of following tree is given 40 / \ 10 30 / \ 5 28 ; Let us test the built tree by printing Insorder traversal
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left ; struct node * right ; } ; int max ( int inorder [ ] , int strt , int end ) ; struct node * newNode ( int data ) ; struct node * buildTree ( int inorder [ ] , int start , int end ) { if ( start > end ) return NULL ; int i = max ( inorder , start , end ) ; struct node * root = newNode ( inorder [ i ] ) ; if ( start == end ) return root ; root -> left = buildTree ( inorder , start , i - 1 ) ; root -> right = buildTree ( inorder , i + 1 , end ) ; return root ; } int max ( int arr [ ] , int strt , int end ) { int i , max = arr [ strt ] , maxind = strt ; for ( i = strt + 1 ; i <= end ; i ++ ) { if ( arr [ i ] > max ) { max = arr [ i ] ; maxind = i ; } } return maxind ; } struct node * newNode ( int 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 ( " % d ▁ " , node -> data ) ; printInorder ( node -> right ) ; } int main ( ) { int inorder [ ] = { 5 , 10 , 40 , 30 , 28 } ; int len = sizeof ( inorder ) / sizeof ( inorder [ 0 ] ) ; struct node * root = buildTree ( inorder , 0 , len - 1 ) ; printf ( " Inorder traversal of the constructed tree is " printInorder ( root ) ; return 0 ; }