Validate a BST
Trees & BST: lesson 6 of 8
Checking the parent is not enough; carry a range down.
Lesson 6 of 8 · 6 min
Validate a BST
Step 1 of 7
Validating carries a range downward. The root inherits (-∞, +∞) — anything goes.
The Idea
Checking that each node beats its own parent is not enough, because a node can satisfy its parent and still break an ancestor's rule. Carry a valid range down instead: stepping left tightens the upper bound, stepping right raises the lower one.
Real-World Example
A construction programme with a hard site-handover date. A subcontractor can beat the deadline their own foreman handed them and still blow the handover, because the real limit was inherited from far above, not from the person standing next to them.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def is_bst(n, low=float('-inf'), high=float('inf')):
if n is None: return True # an empty tree is valid
if not (low < n.val < high): return False # inherited range, not the parent
return (is_bst(n.left, low, n.val) and # going left tightens the cap
is_bst(n.right, n.val, high)) # going right raises the floor
good = Node(5, Node(3), Node(8))
bad = Node(5, Node(3, None, Node(6)), Node(8)) # 6 beats 3 but sits left of 5
print(is_bst(good)) # True
print(is_bst(bad)) # FalseYour turn
Put the steps in the right order.
- Recurse right, using the node's value as the new lower bound
- Return True when the node is empty
- Recurse left, using the node's value as the new upper bound
- Return False if the value falls outside the inherited range
Mini quiz
1 / 3