def is_bst(node)
q = [node]
while q:
node = q.pop(0)
if node:
if node.left:
if not node.left.data < node.data:
return False
q.append(node.left)
if node.right:
if not node.right.data > node.data:
return False
q.append(node.right)
return True
is_bst(root)
On educative.io I worked on this practice problem (paywall), but the gist was that this code didn't work consistently produce the right answers. Their solution used a recursive algorithm. I'd like to know, is it possible to check if a BST is valid iteratively, and if no, what has gone wrong here?
is it possible to check if a BST is valid iteratively
Yes
what has gone wrong here?
Your code only compares a node's value with its direct parent, but even if that test passes for all child-parent pairs, it is not enough to validate a BST. For instance, this tree is not a valid BST, even though all parent-child pairs pass the comparison test:
4
/ \
1 8
/ \
0 5
The value 5 is in violation with the value 4, as all values in the left subtree must not be greater than 4.
To solve this with an iterative algorithm, you could do an inorder traversal (using a stack), and verify that every next value in that traversal is not less than its predecessor:
def is_bst(node):
prev_data = None
q = [] # Not a queue anymore, but a stack
while True:
if node:
q.append(node)
node = node.left
elif q:
node = q.pop()
if prev_data is not None and prev_data > node.data:
return False
prev_data = node.data
node = node.right
else:
return True