DSA & Algorithms
Part 12 of 21 · DSA Interview PatternsBinary Search Trees — Inorder, Bounds, LCA & Validate
BST invariants: inorder sortedness, insert/delete sketch, validate, and LCA.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The tree promises an ordered left and right subtree
Prefer
Use the invariant
Inorder is sorted. Search, insert, and BST LCA are a walk down one path, O(height).
- A parent check is not a range check.
- kth smallest is an inorder count, or subtree sizes if you augment.
- Delete with two children swaps in the inorder successor.
Alternative
Treat it as a plain binary tree
Correct, and slower than the value walk the structure gives you.
- Validating only against the parent.
- Assuming duplicates are forbidden without asking.
- Using the general LCA when both nodes lie on one side.
Walk by value
Equal means found. Smaller goes left. Larger goes right. Validation carries the allowed range.
- 1
Carry an open range
The node must sit strictly between lo and hi. - 2
Walk one side
Both targets smaller: left. Both larger: right. - 3
Otherwise this node splits them
That node is the LCA. Inorder gives kth.
Overview
BST invariants: inorder sortedness, insert/delete sketch, validate, and LCA.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use BST properties: left < node < right, inorder is sorted, search/insert O(h).
Recognition cues
- validate BST
- kth smallest
- LCA of BST (walk by value)
- convert sorted array to BST
Mental model
Decisions
- 1
1. Left subtree is smaller
- next2. Right subtree is larger
- 2
2. Right subtree is larger
- next3. Target equals the node?
- ?
3. Target equals the node?
- yes4. Found
- no5. Target smaller?
- 4
4. Found
- ?
5. Target smaller?
- yes6. Walk left
- no7. Walk right
- 6
6. Walk left
- 7
7. Walk right
Lesson map
Binary Search Trees — Inorder, Bounds, LCA & Validate
BST invariants: inorder sortedness, insert/delete sketch, validate, and LCA.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB n["1. Left subtree is smaller"] r["2. Right subtree is larger"] w["3. Target equals the node?"] found["4. Found"] n -->|1. Left subtree is smaller| r r -->|2. Right subtree is larger| w w -->|yes| found
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Search/insert/LCA walk: O(h); validate/kth: O(n) worst.
- Balanced BST h = O(log n); skewed h = O(n).
Common pitfalls & interview traps
LeetCode drill (real problems)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Lowest Common Ancestor of a Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Delete Node in a BST
- Insert into a Binary Search Tree
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Inorder of BST?
Answer
Sorted ascending (for unique keys).
Validate trap?
Answer
Must enforce open range (lo, hi), not only parent compare.
LCA BST?
Answer
First node between p and q on the search path.
kth smallest?
Answer
Inorder walk counting; or augment subtree sizes.
Balanced build?
Answer
Mid of sorted array as root recursively.
Delete with 2 kids?
Answer
Replace with inorder successor then delete successor.