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.