Check if given Preorder , Inorder and Postorder traversals are of same tree | Python3 program to check if all three given traversals are of the same tree ; A Binary Tree Node ; Function to find index of value in arr [ start ... end ] . The function assumes that value is present in in ; Recursive function to construct binary tree of size lenn from Inorder traversal in and Preorder traversal pre [ ] . Initial values of inStrt and inEnd should be 0 and lenn - 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 ; function to compare Postorder traversal on constructed tree and given Postorder ; first recur on left child ; now recur on right child ; Compare if data at current index in both Postorder traversals are same ; Driver code ; build tree from given Inorder and Preorder traversals ; compare postorder traversal on constructed tree with given Postorder traversal ; If both postorder traversals are same
preIndex = 0 NEW_LINE 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 search ( arr , strt , end , value ) : NEW_LINE INDENT for i in range ( strt , end + 1 ) : NEW_LINE INDENT if ( arr [ i ] == value ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT DEDENT def buildTree ( inn , pre , inStrt , inEnd ) : NEW_LINE INDENT global preIndex NEW_LINE if ( inStrt > inEnd ) : NEW_LINE INDENT return None NEW_LINE DEDENT tNode = node ( pre [ preIndex ] ) NEW_LINE preIndex += 1 NEW_LINE if ( inStrt == inEnd ) : NEW_LINE INDENT return tNode NEW_LINE DEDENT inIndex = search ( inn , inStrt , inEnd , tNode . data ) 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 checkPostorder ( node , postOrder , index ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return index NEW_LINE DEDENT index = checkPostorder ( node . left , postOrder , index ) NEW_LINE index = checkPostorder ( node . right , postOrder , index ) NEW_LINE if ( node . data == postOrder [ index ] ) : NEW_LINE INDENT index += 1 NEW_LINE DEDENT else : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return index NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT inOrder = [ 4 , 2 , 5 , 1 , 3 ] NEW_LINE preOrder = [ 1 , 2 , 4 , 5 , 3 ] NEW_LINE postOrder = [ 4 , 5 , 2 , 3 , 1 ] NEW_LINE lenn = len ( inOrder ) NEW_LINE root = buildTree ( inOrder , preOrder , 0 , lenn - 1 ) NEW_LINE index = checkPostorder ( root , postOrder , 0 ) NEW_LINE if ( index == lenn ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT