Given the root node pointer, check if the tree is a binary search tree. (Each node has parent pointer)

check_if_bst.py

'''
https://en.wikipedia.org/wiki/Binary_search_tree
https://cseweb.ucsd.edu//~kube/cls/100/Lectures/lec5.bst/lec5-1.html
'''



class Node:
    def __init__(self, parent, value):
        self.value = value
        self.parent = parent
        self.left = None
        self.right = None

def check_binary_tree(parent, child):
    if child is None: 
        return True

    if parent != child.parent:
        print("parent is different")
        return False

    if parent.left == child and parent.value <= child.value:
        return False
    
    if parent.right == child and parent.value >= child.value:
        return False

    is_binary = check_binary_tree(child, child.left)
    if is_binary == True:
        return check_binary_tree(child, child.right)
    return is_binary


def verify_bst(root):
    is_binary = check_binary_tree(root, root.left)
    if is_binary == True:
        return check_binary_tree(root, root.right)
    return is_binary

root = Node(None, 10)
c6 = Node(root, 6)
c13 = Node(root, 13)
root.left = c6
root.right = c13

c3 = Node(c6, 3)
c7 = Node(c6, 7)

c6.left = c3
c6.right = c7

c11 = Node(c13, 11)
c14 = Node(c13, 14)

c13.left  = c11
c13.right = c14

c1 = Node(c3, 1)
c4 = Node(c3, 4)

c3.left = c1
c3.right = c4

c8 = Node(c7, 8)
c7.right = c8

is_binary = verify_bst(root)
print("is the tree binary = {}".format(is_binary))