Construct Tree from given Inorder and Preorder traversals | A binary tree node has data , poer to left child and a poer to right child ; Recursive function to construct binary of size len from Inorder traversal in [ ] and Preorder traversal pre [ ] . Initial values of inStrt and inEnd should be 0 and len - 1. The function doesn 't do any error checking for cases where inorder and preorder do not form a tree ; Pick current node from Preorder traversal using preIndex and increment preIndex ; 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 creates an unordered_map , then calls buildTree ( ) ; This funtcion is here just to test buildTree ( ) ; Driver code ; Let us test the built tree by pring Insorder traversal
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 buildTree ( inn , pre , inStrt , inEnd ) : NEW_LINE INDENT global preIndex , mp NEW_LINE if ( inStrt > inEnd ) : NEW_LINE INDENT return None NEW_LINE DEDENT curr = pre [ preIndex ] NEW_LINE preIndex += 1 NEW_LINE tNode = Node ( curr ) NEW_LINE if ( inStrt == inEnd ) : NEW_LINE INDENT return tNode NEW_LINE DEDENT inIndex = mp [ curr ] NEW_LINE tNode . left = buildTree ( inn , pre , inStrt , inIndex - 1 ) NEW_LINE tNode . right = buildTree ( inn , pre , inIndex + 1 , inEnd ) NEW_LINE return tNode NEW_LINE DEDENT def buldTreeWrap ( inn , pre , lenn ) : NEW_LINE INDENT global mp NEW_LINE for i in range ( lenn ) : NEW_LINE INDENT mp [ inn [ i ] ] = i NEW_LINE DEDENT return buildTree ( inn , pre , 0 , lenn - 1 ) NEW_LINE DEDENT def prInorder ( node ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return NEW_LINE DEDENT prInorder ( node . left ) NEW_LINE print ( node . data , end = " ▁ " ) NEW_LINE prInorder ( node . right ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mp = { } NEW_LINE preIndex = 0 NEW_LINE inn = [ ' D ' , ' B ' , ' E ' , ' A ' , ' F ' , ' C ' ] NEW_LINE pre = [ ' A ' , ' B ' , ' D ' , ' E ' , ' C ' , ' F ' ] NEW_LINE lenn = len ( inn ) NEW_LINE root = buldTreeWrap ( inn , pre , lenn ) NEW_LINE print ( " Inorder ▁ traversal ▁ of ▁ " " the ▁ constructed ▁ tree ▁ is " ) NEW_LINE prInorder ( root ) NEW_LINE DEDENT