Practice: Validate a BST
Checking the rule everywhere.
Given a binary tree, check whether it's a valid binary search tree. It's tempting to just check each node against its two children. But that's a trap. Pause, and think about why.

- Is it a valid BST?
- Checking children isn't enough
- Why not?
Passing down limits
The rule must hold for the whole subtree, not just the children. So we pass down the allowed range. Going left, the node's value becomes the new upper limit. Going right, it becomes the new lower limit. Run it. Our sample tree passes. The broken tree fails, because six sits in eight's right subtree, even though it's smaller than eight.
from tree import sample, TreeNode
def valid(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not low < node.value < high:
return False
return valid(node.left, low, node.value) and valid(node.right, node.value, high)
broken = TreeNode(8, TreeNode(3), TreeNode(10, TreeNode(6), TreeNode(12)))
print(valid(sample()))
print(valid(broken))True False
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'Another way
There's a neat second solution. An in order traversal of a valid binary search tree is sorted. So you can list the values in order, and check that each one is bigger than the one before. Both ways are O of N.
| key | value |
|---|---|
| Pass limits | low < value < high |
| Or in order | check it's sorted |
| Trap | only checking children |
| Cost | O(n) |
Summary
Validate a binary search tree by passing down the allowed range, or by checking that in order is sorted. Next, finding the shared ancestor of two nodes.
Key takeaways- Pass low and high
- Left: new high
- Right: new low