Construct Special Binary Tree from given Inorder traversal | C ++ 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 code ; Assume that inorder traversal of following tree is given 40 / \ 10 30 / \ 5 28 ; Let us test the built tree by printing Insorder traversal
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : int data ; node * left ; node * right ; } ; int max ( int inorder [ ] , int strt , int end ) ; node * newNode ( int data ) ; node * buildTree ( int inorder [ ] , int start , int end ) { if ( start > end ) return NULL ; int i = max ( inorder , start , end ) ; 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 ; } node * newNode ( int 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 ( ) { int inorder [ ] = { 5 , 10 , 40 , 30 , 28 } ; int len = sizeof ( inorder ) / sizeof ( inorder [ 0 ] ) ; node * root = buildTree ( inorder , 0 , len - 1 ) ; cout << " Inorder ▁ traversal ▁ of ▁ the ▁ constructed ▁ tree ▁ is ▁ STRNEWLINE " ; printInorder ( root ) ; return 0 ; }