BST Ordering
Use the ordering invariant to skip entire subtrees, and remember that in-order traversal emits sorted values.
Binary Search TreeO(h) for search, O(n) for traversalNew15 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
validate BST
kth smallest
inorder successor
range sum in BST
The template
Get this into muscle memory, then adapt the condition per problem.
function valid(node, lo = -Infinity, hi = Infinity) {
if (!node) return true;
if (node.val <= lo || node.val >= hi) return false;
return valid(node.left, lo, node.val) && valid(node.right, node.val, hi);
} Watch BST Insert & SearchIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Comparing a node only with its direct children is not enough.
- 2Pass down the allowed value window instead.
- 3For kth smallest, count nodes during an in-order walk.
Drill it
Every problem in the bank that uses this pattern.
0 / 15 solved