Find postorder traversal of BST from preorder traversal | Python3 program for finding postorder traversal of BST from preorder traversal ; Function to find postorder traversal from preorder traversal . ; If entire preorder array is traversed then return as no more element is left to be added to post order array . ; If array element does not lie in range specified , then it is not part of current subtree . ; Store current value , to be printed later , after printing left and right subtrees . Increment preIndex to find left and right subtrees , and pass this updated value to recursive calls . ; All elements with value between minval and val lie in left subtree . ; All elements with value between val and maxval lie in right subtree . ; Function to find postorder traversal . ; To store index of element to be traversed next in preorder array . This is passed by reference to utility function . ; Driver Code ; Calling function
INT_MIN = - 2 ** 31 NEW_LINE INT_MAX = 2 ** 31 NEW_LINE def findPostOrderUtil ( pre , n , minval , maxval , preIndex ) : NEW_LINE INDENT if ( preIndex [ 0 ] == n ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( pre [ preIndex [ 0 ] ] < minval or pre [ preIndex [ 0 ] ] > maxval ) : NEW_LINE INDENT return NEW_LINE DEDENT val = pre [ preIndex [ 0 ] ] NEW_LINE preIndex [ 0 ] += 1 NEW_LINE findPostOrderUtil ( pre , n , minval , val , preIndex ) NEW_LINE findPostOrderUtil ( pre , n , val , maxval , preIndex ) NEW_LINE print ( val , end = " ▁ " ) NEW_LINE DEDENT def findPostOrder ( pre , n ) : NEW_LINE INDENT preIndex = [ 0 ] NEW_LINE findPostOrderUtil ( pre , n , INT_MIN , INT_MAX , preIndex ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT pre = [ 40 , 30 , 35 , 80 , 100 ] NEW_LINE n = len ( pre ) NEW_LINE findPostOrder ( pre , n ) NEW_LINE DEDENT