In [ ]:

    

# in an in order traversal, find first node that its key is greater than given k 

class bst:
    def __init__(self, data = 0, left = None, right = None):
        self.data = data
        left = self.left
        right =  right.right
    
def find_first_key(tree):


    

In [ ]:

    

# is a tree a BST

class bst:
    def __init__(self, data = 0, left = None, right = None):
        self.data = data
        left = self.left
        right =  right.right
    
def is_bst(tree, lower = float('-inf'), upper = float('inf')):
    if not tree:
        return true
    
    if not (tree.left <= tree.data <= tree.right):
        return false
    
    return (is_bst(tree.left, float('-inf'), tree.data) and is_bst(tree.right, tree.data, float('inf')))
    

def is_bst_v2(tree, lower = float('-inf'), upper = float('inf')):
    if not tree:
        return true
    
    if not (tree.left <= tree.data <= tree.right):
        return false
    
    return (is_bst(tree.left, float('-inf'), tree.data) and is_bst(tree.right, tree.data, float('inf')))