Check if given sorted sub | Constructor to create a new node ; A utility function to insert a given key to BST ; function to check if given sorted sub - sequence exist in BST index . iterator for given sorted sub - sequence seq [ ] . given sorted sub - sequence ; We traverse left subtree first in Inorder ; If current node matches with se [ index [ 0 ] ] then move forward in sub - sequence ; We traverse left subtree in the end in Inorder ; A wrapper over seqExistUtil . It returns true if seq [ 0. . n - 1 ] exists in tree . ; Initialize index in seq [ ] ; Do an inorder traversal and find if all elements of seq [ ] were present ; index would become n if all elements of seq [ ] were present ; Driver Code
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def insert ( root , key ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return Node ( key ) NEW_LINE DEDENT if root . data > key : NEW_LINE INDENT root . left = insert ( root . left , key ) NEW_LINE DEDENT else : NEW_LINE INDENT root . right = insert ( root . right , key ) NEW_LINE DEDENT return root NEW_LINE DEDENT def seqExistUtil ( ptr , seq , index ) : NEW_LINE INDENT if ptr == None : NEW_LINE INDENT return NEW_LINE DEDENT seqExistUtil ( ptr . left , seq , index ) NEW_LINE if ptr . data == seq [ index [ 0 ] ] : NEW_LINE INDENT index [ 0 ] += 1 NEW_LINE DEDENT seqExistUtil ( ptr . right , seq , index ) NEW_LINE DEDENT def seqExist ( root , seq , n ) : NEW_LINE INDENT index = [ 0 ] NEW_LINE seqExistUtil ( root , seq , index ) NEW_LINE if index [ 0 ] == n : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = insert ( root , 8 ) NEW_LINE root = insert ( root , 10 ) NEW_LINE root = insert ( root , 3 ) NEW_LINE root = insert ( root , 6 ) NEW_LINE root = insert ( root , 1 ) NEW_LINE root = insert ( root , 4 ) NEW_LINE root = insert ( root , 7 ) NEW_LINE root = insert ( root , 14 ) NEW_LINE root = insert ( root , 13 ) NEW_LINE seq = [ 4 , 6 , 8 , 14 ] NEW_LINE n = len ( seq ) NEW_LINE if seqExist ( root , seq , n ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT