Check if a binary tree is a BST

One obvious way to do it is to do a inorder traversal, build a list as we go and check if the final list is sorted. In theory we don’t even need the whole array, comparing currentNode.key and previousNode.key should be enough.

def isBST(t):

    def buildList(t):
        if t:
            buildList(t.left)
            values.append(t.key)
            buildList(t.right)

    values = []
    buildList(t)

    if sorted(values) == values:
        return True
        
    return False

The other, somehow fancier way to do it, rests on the idea that in a BST every node (key) has the following constraints:

  1. *ALL* the left nodes must be <= than the current node
  2. *ALL* the right nodes must be > than the current node

A way to implement these constraints is to check that every node is within a range:

  1. when we branch left, the MAX gets updated to currentNode.value
  2. when we branch right, the MIN gets updated to currentNode.value
  3. if any node is not within the range, we stop and return False
def isBST(node, MIN=1, MAX=100):
    
    if node is None:
        return True

    if node.key < MIN or node.key > MAX:
        return False

    return isBST(node.left, MIN, node.key) 
           and
           isBST(node.right, node.key, MAX) 

the MIN and MAX args specify the domain of the keys accepted.