# 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.