about summary refs log blame commit diff
path: root/users/wpcarro/scratch/facebook/interview-cake/bst-checker.py
blob: bbd52fa9c64cf903c356a23ddf899d2ff571a17f (plain) (tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14













                                                             
def is_valid(node):
    """
    Return True if `node` is a valid binary search tree.
    """
    s = []
    s.append((float('-inf'), node, float('inf')))
    while s:
        lo, node, hi = s.pop()
        if lo <= node.value <= hi:
            node.lhs and s.append((lo, node.lhs, node.value))
            node.rhs and s.append((node.value, node.rhs, hi))
        else:
            return False
    return True