← Back to the trees page
Binary Search Tree (BST)
Left < node < right, recursively. Inorder traversal yields sorted order — that single fact powers most BST interview questions.
What to know
- All operations are O(h); h is log n only if the tree stays balanced.
- Validation needs min/max bounds passed down, not just parent-child checks.
- Delete has three cases; the two-children case swaps in the inorder successor.
- Sorted-order problems (kth smallest, closest value, range sums) fall to inorder walks.
In the wild: In-memory ordered maps, database index prototypes, autocompletion rankers.
Algorithms to reach for
Search / insert / delete
O(h)Ordered dictionary operations
Validate BST with bounds
O(n)Confirm the global invariant (LeetCode 98)
Kth smallest via inorder
O(h + k)Order statistics without full sort (LeetCode 230)
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.