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.