Construct Special Binary Tree from given Inorder traversal | 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 class that allocates a new node with the given data and None 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
def buildTree ( inorder , start , end ) : NEW_LINE INDENT if start > end : NEW_LINE INDENT return None NEW_LINE DEDENT i = Max ( inorder , start , end ) NEW_LINE root = newNode ( inorder [ i ] ) NEW_LINE if start == end : NEW_LINE INDENT return root NEW_LINE DEDENT root . left = buildTree ( inorder , start , i - 1 ) NEW_LINE root . right = buildTree ( inorder , i + 1 , end ) NEW_LINE return root NEW_LINE DEDENT def Max ( arr , strt , end ) : NEW_LINE INDENT i , Max = 0 , arr [ strt ] NEW_LINE maxind = strt NEW_LINE for i in range ( strt + 1 , end + 1 ) : NEW_LINE INDENT if arr [ i ] > Max : NEW_LINE INDENT Max = arr [ i ] NEW_LINE maxind = i NEW_LINE DEDENT DEDENT return maxind NEW_LINE DEDENT class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def printInorder ( node ) : NEW_LINE INDENT if node == None : NEW_LINE INDENT return NEW_LINE DEDENT printInorder ( node . left ) NEW_LINE print ( node . data , end = " ▁ " ) NEW_LINE printInorder ( node . right ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT inorder = [ 5 , 10 , 40 , 30 , 28 ] NEW_LINE Len = len ( inorder ) NEW_LINE root = buildTree ( inorder , 0 , Len - 1 ) NEW_LINE print ( " Inorder ▁ traversal ▁ of ▁ the " , " constructed ▁ tree ▁ is ▁ " ) NEW_LINE printInorder ( root ) NEW_LINE DEDENT