BST
How BST works
Before you start
- Open lesson
Binary Search
A BST is binary search frozen into a tree. Each step down discards one side.
Why it matters
Ordered maps and database indexes rely on BST ordering to discard large regions during lookup. A single misplaced descendant can leave all parent-child comparisons looking valid while sending searches down the wrong branch. Validation must reject any value that violates a distant ancestor's range, not only a direct parent's order.
Example
Validate Binary Search Tree
Return true if root is a valid BST: every value in the left subtree is strictly less than the node, and every value on the right is strictly greater.
- Input
- root = [5, 1, 7, None, None, 4, 8]
- Output
- False
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Validate Binary Search Tree
root = [5, 1, 7, None, None, 4, 8]→False
The baseline, Inorder into a list, is O(n) · O(n). The better model below keeps this exact input and removes that bottleneck.
For [5, 1, 7, None, None, 4, 8], the brute inorder list stores every value before noticing 4 follows 5. Carry the range (5, 7) to node 4 instead, so the violation is detected without that list.
In [5, 1, 7, None, None, 4, 8], node 5 starts with the range (−∞, ∞). Its right child 7 inherits 5 as its lower bound. Moving left from 7 keeps that lower bound and changes the upper bound to 7.
Node 4 is smaller than its parent 7, but it does not satisfy 5 < 4 < 7, so the check returns False. Node 1 fits (−∞, 5) and node 8 would fit (7, ∞), but every node must satisfy the full range inherited from its ancestors.
Visual anchor
Validate Binary Search Tree
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.