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

- *ALL* the left nodes must be <= than the current node
- *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:

- when we branch left, the MAX gets updated to currentNode.value
- when we branch right, the MIN gets updated to currentNode.value
- 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.