1Understand
The idea
In a binary search tree every node is greater than everything in its left subtree and smaller than everything in its right subtree. So a search can follow one path from the root (O(h)), and an in-order traversal visits values in sorted order. Validating means checking that range for every node, not just its children.
Intuition
In a BST every node is greater than everything in its left subtree and smaller than everything in its right. A search therefore follows one path from the root, O(h), not O(n).
In-order traversal visits values in sorted order. Validating a BST means checking the allowed range for every node (low, high), not only comparing each node to its immediate children, a classic trap.
Insert and delete maintain the same ordering invariant; balanced BSTs keep h = O(log n), skewed trees degrade to O(n).
What you will be able to do
- Pass bounds down the recursion
- Use in-order traversal for sorted order
When to use it
- Input is a BST
- Validate BST
- K-th smallest, in-order successor
2See it
Walkthrough
BST search
Inorder values [1, 2, 3, 4, 5], target = 4, go left/right by comparison.
1 / 5
Root 3. Target 4 > 3 → entire left subtree (<3) is ruled out.
Live template
Line 1 active
Complexity: time O(h) to O(n), space O(h)
Search/insert expected O(h). Validation is O(n). Space O(h) recursion. If you only compare to children, you accept illegal trees, always thread the range or use in-order.
Read the walkthrough as text
Validate BST. Tree: 5 with left 1, right 8 with left 6 and right 9, valid. If 6 were 4, children of 5 still look fine locally but 4 is not > 5.
- Call
ok(node, lo, hi)with open bounds. - At
5, checklo < 5 < hi, then left withhi=5, right withlo=5. - At
6, require5 < 6 < 8. A4would fail> 5.
In-order and checking non-decreasing values is an equivalent approach.
3Recognise it
Kinds of problems (8)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Search / insert / delete
Example. Design a BST that supports search, insert and delete.
How. Compare at each node and recurse left or right; delete uses successor for two children.
Validate a BST
Example. Return false if any node breaks the global BST order.
How. Pass (lo, hi) bounds down the recursion; node.val must stay strictly inside.
K-th smallest (in-order)
Example. K-th smallest value in a BST.
How. In-order traversal with a counter; stop at the k-th visited node.
LCA in a BST
Example. Lowest common ancestor when both keys exist in the BST.
How. Walk from root: split when one key is left and one is right, that node is the LCA.
Build a balanced BST from sorted data
Example. Construct a height-balanced BST from a sorted array.
How. Recursively pick mid as root; left half builds left subtree, right half the right.
BST iterator (in-order with an explicit stack)
Example. Iterator with next() and hasNext() in O(h) amortised.
How. Push left spine to stack; next pops, then push left chain of right child.
Neighbouring or reverse in-order (min gap, greater tree)
Example. Minimum absolute difference in BST, or replace each value with next greater.
How. In-order records previous value or propagates running “next” backward through recursion.
Trim or restructure by a value range
Example. Trim nodes outside [low, high] while keeping a valid BST.
How. Recurse; drop whole subtrees when node.val is outside range; reattach children when inside.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Only checks children
Why it happens. Checking only parent against children matches how BSTs are drawn locally.
How it fails. Left child 3 with parent 5 but ancestor 2 on the path, local check passes, global BST rule fails.
Fix. Pass (lo, hi) open bounds down the recursion; node.val must satisfy lo < val < hi.
Ignores ordering
Why it happens. When search misses, exploring both sides feels thorough.
How it fails. target = 5 in BST with root 8, you search both subtrees in O(n) instead of going left once.
Fix. Compare to root: smaller → left only, larger → right only.
Delete with two children
Why it happens. Deleting by linking children directly is the obvious fix.
How it fails. Remove node with two children without successor, middle order breaks and search returns wrong nodes.
Fix. Replace with inorder successor (min of right subtree), then delete duplicate leaf.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.