Interview Cake problem: verify a binary search tree https://www.interviewcake.com/question/python/bst-checker

check.py

#!/usr/bin/env python

# Intervie Cake problem: verify a binary search tree.
# See https://www.interviewcake.com/question/python/bst-checker

class BinarySearchTree(object):

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

    def insert_left(self, value):
        self.left = BinarySearchTree(value)
        return self.left
    
    def insert_right(self, value):
        self.right = BinarySearchTree(value)
        return self.right


# return the first among (a, b) which is not None.
def some(a, b):
    if a is not None:
        return a
    else:
        return b


# recursively walk the tree and determine if it is a valid binary search tree.
# returns a triple of (<valid>, <min value>, <max value>)
# valid tree: (True, <min>, <max>)
# invalid tree: (False, None, None)
# nil tree: (None, None, None)
def recurse_and_verify(tree):
    if tree is None:
        return (None, None, None)

    (lvalid, lmin, lmax) = recurse_and_verify(tree.left)
    (rvalid, rmin, rmax) = recurse_and_verify(tree.right)

    if lvalid == False or rvalid == False:
        return (False, None, None)
    elif lmax is not None and lmax >= tree.value:
        print "tree is invalid because lmax (%s) >= tree.value (%s)" % (lmax, tree.value)
        return (False, None, None)
    elif rmin is not None and rmin <= tree.value:
        print "tree is invalid because rmax (%s) <= tree.value (%s)" % (rmax, tree.value)
        return (False, None, None)
    else:
        tmin = some(lmin, tree.value)
        tmax = some(rmax, tree.value)
        return (True, tmin, tmax)


def lesser(a, b):
    if a is None and b is None:
        return None
    if a is None:
        return b
    if b is None:
        return a
    return min(a, b)

def greater(a, b):
    if a is None and b is None:
        return None
    if a is None:
        return b
    if b is None:
        return a
    return max(a, b)

def iterate_and_verify(tree):
    if tree is None:
        return None
    stack = [(tree, None, None)]
    while len(stack):
        (node, min_ancestor, max_ancestor) = stack.pop()
        if node.left:
            if node.left.value >= node.value:
                print "tree is invalid because node.left.value (%s) >= node.value (%s)" % (node.left.value, node.value)
                return False
            if min_ancestor and node.left.value <= min_ancestor:
                print "tree is invalid because node.left.value (%s) <= min_ancestor (%s)" % (node.left.value, min_ancestor)
                return False
            else:
                stack.append((node.left, min_ancestor, greater(max_ancestor, node.value)))
        if node.right:
            if node.right.value <= node.value:
                print "tree is invalid because node.right.value (%s) <= node.value (%s)" % (node.right.value, node.value)
                return False
            if max_ancestor and node.right.value >= max_ancestor:
                print "tree is invalid because node.right.value (%s) >= max_ancestor (%s)" % (node.right.value, max_ancestor)
                return False
            else:
                stack.append((node.right, lesser(min_ancestor, node.value), max_ancestor))
    return True


def verify(tree):
    # return recurse_and_verify(tree)[0]
    return iterate_and_verify(tree)


def test1():
    # tree:
    #  <nil>
    print "test1"
    assert verify(None) is None

def test2():
    # tree:
    #   5
    print "test2"
    root = BinarySearchTree(5)
    assert verify(root) is True

def test3():
    # tree:
    #   5
    #  /
    # 3
    print "test3"
    root = BinarySearchTree(5)
    root.insert_left(3)
    assert verify(root) is True

def test4():
    # tree:
    #   5
    #  /
    # 6
    print "test4"
    root = BinarySearchTree(5)
    root.insert_left(6)
    assert verify(root) is False

def test5():
    # tree:
    #     5
    #    /
    #   3
    #  /
    # 2
    print "test5"
    root = BinarySearchTree(5)
    node = root.insert_left(3)
    node.insert_left(2)
    assert verify(root) is True

def test6():
    # tree:
    #     5
    #    /
    #   3
    #  / \
    # 2   1
    print "test6"
    root = BinarySearchTree(5)
    node = root.insert_left(3)
    node.insert_left(2)
    node.insert_right(1)
    assert verify(root) is False

def test7():
    # tree:
    #     5
    #    /
    #   3
    #  / \
    # 2   4
    print "test7"
    root = BinarySearchTree(5)
    node = root.insert_left(3)
    node.insert_left(2)
    node.insert_right(4)
    assert verify(root) is True

def test8():
    # tree:
    #     5
    #    /
    #   3
    #  / \
    # 2   6
    print "test8"
    root = BinarySearchTree(5)
    node = root.insert_left(3)
    node.insert_left(2)
    node.insert_right(6)
    assert verify(root) is False


# thanks to peter:

def build_tree_iteratively(items):
    head_node = None
    values = []
    for i, item in enumerate(items):
        if i == 0:
            head_node = BinarySearchTree(item)
            continue
        else:
            values.append((head_node, item))

    while len(values):
        value_tuple = values.pop(0)
        node = value_tuple[0]
        value = value_tuple[1]

        if value < node.value:
            if node.left:
                values.insert(0, (node.left, value))
            else:
                node.insert_left(value)
        elif value > node.value:
            if node.right:
                values.insert(0, (node.right, value))
            else:
                node.insert_right(value)

    return head_node

def test9():
    #        8
    #      /   \
    #     3     10
    #    /  \      \
    #   1    6      14
    #       /  \    /
    #      4    7  13
    print "test9"
    root = build_tree_iteratively([8, 3, 10, 14, 6, 1, 4, 2, 7, 13])
    # root = BinarySearchTree(8)
    # node = root.insert_left(3)
    # node.insert_left(1)
    # node = node.insert_right(6)
    # node.insert_left(4)
    # node.insert_right(7)
    # node = root.insert_right(10)
    # node = node.insert_right(14)
    # node.insert_left(13)
    assert verify(root) == True


if __name__ == "__main__":
    test1()
    test2()
    test3()
    test4()
    test5()
    test6()
    test7()
    test8()
    test9()
    print "all tests passed"