Construct a Binary Tree from Postorder and Inorder | A binary tree node has data , pointer to left child and a pointer to right child ; 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 finnd the inndex of this node inn Inorder traversal ; Using inndex inn Inorder traversal , construct left and right subtress ; This function mainly creates an unordered_map , then calls buildTreeUtil ( ) ; Store indexes of all items so that we we can quickly find later ; Index in postorder ; This funtcion is here just to test ; Driver Code
class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def buildUtil ( inn , post , innStrt , innEnd ) : NEW_LINE INDENT global mp , index NEW_LINE if ( innStrt > innEnd ) : NEW_LINE INDENT return None NEW_LINE DEDENT curr = post [ index ] NEW_LINE node = Node ( curr ) NEW_LINE index -= 1 NEW_LINE if ( innStrt == innEnd ) : NEW_LINE INDENT return node NEW_LINE DEDENT iIndex = mp [ curr ] NEW_LINE node . right = buildUtil ( inn , post , iIndex + 1 , innEnd ) NEW_LINE node . left = buildUtil ( inn , post , innStrt , iIndex - 1 ) NEW_LINE return node NEW_LINE DEDENT def buildTree ( inn , post , lenn ) : NEW_LINE INDENT global index NEW_LINE for i in range ( lenn ) : NEW_LINE INDENT mp [ inn [ i ] ] = i NEW_LINE DEDENT index = lenn - 1 NEW_LINE return buildUtil ( inn , post , 0 , lenn - 1 ) NEW_LINE 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 inn = [ 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 ] NEW_LINE post = [ 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 ] NEW_LINE n = len ( inn ) NEW_LINE mp , index = { } , 0 NEW_LINE root = buildTree ( inn , post , n ) NEW_LINE print ( " Preorder ▁ of ▁ the ▁ constructed ▁ tree ▁ : " ) NEW_LINE preOrder ( root ) NEW_LINE DEDENT