Construct a Binary Tree from Postorder and Inorder | Recursive function to construct binary of size n from Inorder traversal in [ ] and Postorder traversal post [ ] . Initial values of inStrt and inEnd should be 0 and n - 1. The function doesn 't do any error checking for cases where inorder and postorder do not form a tree ; Base case ; Pick current node from Postorder traversal using postIndex and decrement postIndex ; 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 ; This function mainly initializes index of root and calls buildUtil ( ) ; Function to find index of value in arr [ start ... end ] . The function assumes that value is postsent in in [ ] ; Helper function that allocates a new node ; This funtcion is here just to test ; Driver code
def buildUtil ( In , post , inStrt , inEnd , pIndex ) : NEW_LINE INDENT if ( inStrt > inEnd ) : NEW_LINE INDENT return None NEW_LINE DEDENT node = newNode ( post [ pIndex [ 0 ] ] ) NEW_LINE pIndex [ 0 ] -= 1 NEW_LINE if ( inStrt == inEnd ) : NEW_LINE INDENT return node NEW_LINE DEDENT iIndex = search ( In , inStrt , inEnd , node . data ) NEW_LINE node . right = buildUtil ( In , post , iIndex + 1 , inEnd , pIndex ) NEW_LINE node . left = buildUtil ( In , post , inStrt , iIndex - 1 , pIndex ) NEW_LINE return node NEW_LINE DEDENT def buildTree ( In , post , n ) : NEW_LINE INDENT pIndex = [ n - 1 ] NEW_LINE return buildUtil ( In , post , 0 , n - 1 , pIndex ) NEW_LINE DEDENT def search ( arr , strt , end , value ) : NEW_LINE INDENT i = 0 NEW_LINE for i in range ( strt , end + 1 ) : NEW_LINE INDENT if ( arr [ i ] == value ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return i NEW_LINE DEDENT class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def preOrder ( node ) : NEW_LINE INDENT if node == None : NEW_LINE INDENT return NEW_LINE DEDENT print ( node . data , end = " ▁ " ) NEW_LINE preOrder ( node . left ) NEW_LINE preOrder ( node . right ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT In = [ 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 ] NEW_LINE post = [ 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 ] NEW_LINE n = len ( In ) NEW_LINE root = buildTree ( In , post , n ) NEW_LINE print ( " Preorder ▁ of ▁ the ▁ constructed ▁ tree ▁ : " ) NEW_LINE preOrder ( root ) NEW_LINE DEDENT