Binary Search Tree (BST) — The Complete Guide
Master BSTs from first principles. Learn to exploit the sorted-order property, recognize BST problems instantly, validate trees, and confidently solve every BST-based interview question.
Table of Contents
Intuition from Scratch
Why does this pattern exist?
A Binary Search Tree is a binary tree with one powerful rule: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This single constraint turns a tree into a sorted structure that supports search, insert, and delete in O(h) time, where h is the height.
Think of it this way: a sorted array gives you O(log n) search via binary search, but inserting or deleting is O(n) because you have to shift elements. A BST gives you O(log n) for search, insert, AND delete (when balanced) — it's the best of both worlds. The tree structure means you never shift anything; you just rearrange pointers.
The most important property of a BST is that an inorder traversal (left → node → right) visits nodes in sorted ascending order. This single fact is the key to solving almost every BST interview problem. If you remember nothing else, remember this: inorder traversal of a BST = sorted array.
How a BST Works (The Basics)
BST Rule: left < node < right (for every node) Example BST: 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 Inorder traversal: 1, 3, 4, 6, 7, 8, 10, 13, 14 ← SORTED! Search for 7: 8 → go left (7 < 8) 3 → go right (7 > 3) 6 → go right (7 > 6) 7 → found! (3 comparisons instead of scanning all 9 nodes) Key operations (balanced BST): search(val) → O(log n) — binary search down the tree insert(val) → O(log n) — find the right spot, add leaf delete(val) → O(log n) — find node, handle 3 cases min / max → O(log n) — go all the way left / right inorder() → O(n) — visit all nodes in sorted order
Analogies to Build Intuition
A Dictionary
A dictionary is organized alphabetically. To find a word, you don't scan every page — you open to the middle, decide if your word is before or after, and repeat. A BST works the same way: at each node, you decide left or right. The sorted structure eliminates half the remaining options at every step.
A Company Org Chart
Imagine an org chart where every manager's employee number is between their left and right reports. To find employee #42, you start at the CEO and go left if 42 is smaller, right if larger. You never visit the wrong department. That's a BST — the structure itself guides you to the answer.
Piano Keys in a Tree
Imagine arranging piano keys in a tree where each key's left subtree has lower notes and right subtree has higher notes. Playing the keys by visiting left-node-right (inorder) produces a perfect ascending scale. That's the BST's superpower — inorder traversal always gives sorted output.
What kind of problems does it solve?
BSTs are your go-to when:
- You need to validate if a tree is a BST — check the sorted-order invariant
- You need to find the Kth smallest/largest element in a tree
- You need to find the lowest common ancestor — BST property lets you do it in O(h)
- You need to convert between BST and sorted array/list
- You need to search, insert, or delete in a sorted dynamic collection
- You need to find inorder successor/predecessor of a node
- You need to construct a balanced BST from sorted data
The core insight
The BST property means inorder traversal = sorted order. Almost every BST problem reduces to exploiting this fact. When you see a BST problem, your first thought should be: "How does the sorted-order property help me here?"
Pattern Recognition
Recognizing when the BST property is the key insight is the most important skill. Here are the signals to look for and the traps to avoid.
Keywords & Signals in the Problem Statement
Use BST techniques when you see...
- ✅"Validate BST" or "check if binary tree is a BST"
- ✅"Kth smallest element in a BST"
- ✅"Lowest common ancestor in a BST" (not generic tree)
- ✅"Convert sorted array/list to BST"
- ✅"Inorder successor" or "inorder predecessor"
- ✅"Search in a BST" or "insert into a BST"
- ✅"Delete node in a BST"
- ✅"Recover BST" — two nodes swapped
- ✅"BST iterator" — next smallest element
- ✅Any problem that explicitly says "binary search tree"
Don't use BST techniques when...
- ❌The tree is a generic binary tree (not BST) — use general tree traversal
- ❌You need the Kth largest in an array — use a Heap, not a BST
- ❌The problem is about tree structure (depth, diameter) — use DFS/BFS
- ❌You need to find paths or sums in a generic tree — use tree DFS
- ❌The problem involves a trie (prefix tree) — different data structure
- ❌You need balanced operations guaranteed — use a self-balancing tree (AVL/Red-Black)
BST vs. Similar Patterns
| Pattern | When to Use | Key Difference |
|---|---|---|
| BST | Sorted-order property matters: validate, Kth element, LCA, search/insert/delete | Exploits left < node < right invariant; inorder = sorted |
| General Binary Tree | Structure-based problems: depth, diameter, path sum, serialize | No ordering guarantee — must visit all nodes |
| Heap / Priority Queue | Top-K, streaming min/max, merge K sorted | Only guarantees root is min/max — not fully sorted like BST |
| Binary Search (Array) | Search in sorted array, find boundaries | Same O(log n) search idea, but on arrays — no insert/delete advantage |
| Trie (Prefix Tree) | String prefix matching, autocomplete, word search | Branching by characters, not by value comparison |
| AVL / Red-Black Tree | Need guaranteed O(log n) operations | Self-balancing BSTs — same BST property but with height guarantees |
The BST question to always ask
When you see a tree problem, ask: "Is this a BST, and does the sorted-order property help?" If the problem says BST, you almost certainly need to exploit the ordering. If it's a generic binary tree, BST techniques won't apply — use general tree traversal instead.
Brute Force → Optimized Thinking
Let's walk through the thinking evolution using a concrete example: Kth Smallest Element in a BST — given a BST and an integer k, return the kth smallest element.
Brute Force — Collect All, Sort, Index
Traverse the entire tree, collect all values into an array, sort the array, and return the (k-1)th element. This completely ignores the BST property — you're treating it like a generic tree.
function kthSmallestBrute(root: TreeNode | null, k: number): number { const values: number[] = []; function collect(node: TreeNode | null) { if (!node) return; collect(node.left); values.push(node.val); collect(node.right); } collect(root); values.sort((a, b) => a - b); return values[k - 1]; } // Problem: We collect ALL n values and sort them. // We're ignoring the fact that inorder traversal is already sorted!
Better — Inorder Traversal (Full)
Key insight: inorder traversal of a BST visits nodes in sorted order. So just do an inorder traversal, collect into an array, and return the (k-1)th element. No sorting needed — the BST does it for you.
function kthSmallestInorder(root: TreeNode | null, k: number): number { const sorted: number[] = []; function inorder(node: TreeNode | null) { if (!node) return; inorder(node.left); sorted.push(node.val); inorder(node.right); } inorder(root); return sorted[k - 1]; } // Better: O(n) time, no sorting needed. // But we still visit ALL n nodes even if k = 1.
Optimal — Early-Stop Inorder
We don't need to traverse the entire tree. Since inorder visits nodes in sorted order, we just count: when we've visited k nodes, we have our answer. Stop immediately — don't visit the remaining n-k nodes.
function kthSmallest(root: TreeNode | null, k: number): number { let count = 0; let result = 0; function inorder(node: TreeNode | null) { if (!node || count >= k) return; // early stop inorder(node.left); count++; if (count === k) { result = node.val; return; // found it — stop immediately } inorder(node.right); } inorder(root); return result; } // Time: O(k) — we stop after visiting k nodes // Space: O(h) — recursion stack depth = tree height // When k = 1, we only visit the leftmost path. When k = n, we visit all.
Why Does the Optimization Work?
Inorder traversal IS the sorted order
The BST property guarantees that visiting left → node → right produces values in ascending order. This eliminates the need to sort — the tree structure is the sort.
Early stopping avoids unnecessary work
Once we've counted k nodes in inorder, we have the kth smallest. There's no reason to visit the remaining n-k nodes. The early-stop condition (count >= k) prunes the right subtree entirely.
The general principle
Almost every BST optimization follows this pattern: 'Use the BST property to avoid visiting nodes you don't need.' For search, you skip half the tree at each step. For Kth smallest, you stop after k nodes. The BST property is your pruning tool.
The thinking process matters more than the code
In interviews, walk through this progression: "Brute force collects and sorts — O(n log n). But inorder traversal of a BST is already sorted — O(n). And since I only need the kth element, I can stop after k nodes — O(k)." This shows the interviewer you understand WHY the BST property helps at each step.
Core Templates
BST problems follow a few recurring templates. Memorize these structures — most problems are variations of one of them.
Template 1: BST Validation (Min/Max Range)
Every node must fall within a valid range. The root can be anything. Going left tightens the upper bound. Going right tightens the lower bound. If any node violates its range, the tree is not a BST.
function isValidBST(root: TreeNode | null): boolean { function validate( node: TreeNode | null, min: number, max: number ): boolean { if (!node) return true; // Current node must be within (min, max) — exclusive if (node.val <= min || node.val >= max) return false; // Left subtree: tighten upper bound to node.val // Right subtree: tighten lower bound to node.val return ( validate(node.left, min, node.val) && validate(node.right, node.val, max) ); } return validate(root, -Infinity, Infinity); } // Time: O(n) — visit each node once // Space: O(h) — recursion stack // Key: pass min/max bounds down. Don't just check parent-child — // check against the ENTIRE ancestor chain via the range.
Template 2: BST Search (Go Left or Right)
The BST property lets you eliminate half the tree at each step. If the target is smaller, go left. If larger, go right. This is binary search on a tree.
function searchBST(root: TreeNode | null, val: number): TreeNode | null { let curr = root; while (curr) { if (val === curr.val) return curr; if (val < curr.val) curr = curr.left; else curr = curr.right; } return null; // not found } // Time: O(h) — h is tree height (O(log n) if balanced) // Space: O(1) — iterative, no recursion stack // Variation: insert follows the same path but adds a new leaf // Variation: LCA in BST uses the same left/right decision
Template 3: Inorder Traversal with State
Inorder traversal visits BST nodes in sorted order. Carry state (counter, previous value, etc.) through the traversal to answer questions about the sorted sequence without building an array.
// Example: Kth Smallest — count during inorder function kthSmallest(root: TreeNode | null, k: number): number { let count = 0; let result = 0; function inorder(node: TreeNode | null) { if (!node || count >= k) return; inorder(node.left); count++; if (count === k) { result = node.val; return; } inorder(node.right); } inorder(root); return result; } // Example: Validate BST via inorder — check prev < curr function isValidBSTInorder(root: TreeNode | null): boolean { let prev = -Infinity; function inorder(node: TreeNode | null): boolean { if (!node) return true; if (!inorder(node.left)) return false; if (node.val <= prev) return false; prev = node.val; return inorder(node.right); } return inorder(root); } // When to use: Kth smallest, validate BST, recover BST, // BST to sorted list, minimum difference in BST
Template 4: Build BST from Sorted Data
To build a balanced BST from sorted data, pick the middle element as root, recursively build the left subtree from the left half and the right subtree from the right half. This guarantees O(log n) height.
function sortedArrayToBST(nums: number[]): TreeNode | null { function build(left: number, right: number): TreeNode | null { if (left > right) return null; const mid = Math.floor((left + right) / 2); const node = new TreeNode(nums[mid]); node.left = build(left, mid - 1); node.right = build(mid + 1, right); return node; } return build(0, nums.length - 1); } // Time: O(n) — visit each element once // Space: O(log n) — recursion depth of balanced tree // Key: middle element = root guarantees balance. // Same idea works for sorted linked list → BST (use slow/fast pointer for mid).
Which template to pick?
Ask yourself: (1) Am I checking if a tree is a valid BST? → Template 1. (2) Am I searching, inserting, or finding LCA? → Template 2. (3) Am I answering a question about the sorted order (Kth, min diff, recover)? → Template 3. (4) Am I building a BST from sorted input? → Template 4.
Variations & Sub-Patterns
BST problems aren't a single trick — they're a family of techniques that all exploit the sorted-order property in different ways.
| Variation | BST Strategy | Classic Example |
|---|---|---|
| Validation | Pass min/max range down, or check inorder is strictly increasing | Validate BST, Recover BST |
| Search / Insert / Delete | Binary search down the tree — go left or right at each node | Search in BST, Insert into BST, Delete Node in BST |
| Kth Element | Inorder traversal with early stop at count = k | Kth Smallest Element, Kth Largest (reverse inorder) |
| LCA in BST | Split point: first node where p and q diverge to different subtrees | Lowest Common Ancestor of a BST |
| Construction | Pick middle of sorted data as root, recurse on halves | Sorted Array to BST, Sorted List to BST |
| Conversion | Inorder traversal to flatten BST into sorted list or vice versa | BST to Sorted Doubly Linked List, Flatten BST to Sorted List |
| Iterator | Controlled inorder using an explicit stack — push all lefts, pop, go right | BST Iterator, Inorder Successor |
| Recovery | Inorder traversal to find the two swapped nodes (where sorted order breaks) | Recover BST |
Problems mentioned above
Deep Dive: LCA in BST — The Split Point
In a generic binary tree, LCA requires visiting both subtrees. But in a BST, you can find the LCA in O(h) by exploiting the ordering: the LCA is the first node where p and q "split" — one goes left and the other goes right (or one equals the current node).
function lowestCommonAncestor( root: TreeNode | null, p: TreeNode, q: TreeNode ): TreeNode | null { let curr = root; while (curr) { if (p.val < curr.val && q.val < curr.val) { curr = curr.left; // both in left subtree } else if (p.val > curr.val && q.val > curr.val) { curr = curr.right; // both in right subtree } else { return curr; // split point — this is the LCA } } return null; } // Time: O(h) — follow one path down the tree // Space: O(1) — iterative // Key: in a BST, if p < node < q (or p = node or q = node), // then node is the LCA. No need to search both subtrees.
Deep Dive: Delete Node in BST — Three Cases
Deletion is the trickiest BST operation because you must maintain the BST property after removing a node. There are three cases depending on how many children the node has.
function deleteNode(root: TreeNode | null, key: number): TreeNode | null { if (!root) return null; if (key < root.val) { root.left = deleteNode(root.left, key); } else if (key > root.val) { root.right = deleteNode(root.right, key); } else { // Found the node to delete — 3 cases: // Case 1: Leaf node — just remove it if (!root.left && !root.right) return null; // Case 2: One child — replace with that child if (!root.left) return root.right; if (!root.right) return root.left; // Case 3: Two children — replace with inorder successor // (smallest node in right subtree) let successor = root.right; while (successor.left) successor = successor.left; root.val = successor.val; // copy successor's value root.right = deleteNode(root.right, successor.val); // delete successor } return root; } // Time: O(h) — search + find successor + delete successor // Space: O(h) — recursion stack // Key: Case 3 is the tricky one. The inorder successor is the // smallest node in the right subtree — it has no left child, // so deleting it is Case 1 or Case 2 (easy).
Deep Dive: BST Iterator — Controlled Inorder
A BST iterator returns elements in sorted order one at a time. Instead of doing a full inorder traversal upfront, use an explicit stack to "pause" the traversal between calls.
class BSTIterator { private stack: TreeNode[] = []; constructor(root: TreeNode | null) { this.pushAllLeft(root); } // Push node and all its left descendants onto the stack private pushAllLeft(node: TreeNode | null) { while (node) { this.stack.push(node); node = node.left; } } next(): number { const node = this.stack.pop()!; // After visiting a node, process its right subtree this.pushAllLeft(node.right); return node.val; } hasNext(): boolean { return this.stack.length > 0; } } // next() and hasNext() are O(1) amortized, O(h) worst case // Space: O(h) — stack holds at most h nodes (one path) // Key: the stack simulates the recursion stack of inorder traversal. // pushAllLeft goes as far left as possible (like the recursive call). // After popping (visiting), we process the right subtree.
Visual Walkthrough
Let's trace through three classic BST problems step by step to see the patterns in action.
Validate BST (Min/Max Range) — Step by Step
Tree: 5 / \ 1 7 / \ 6 8 validate(5, -∞, +∞) 5 is in (-∞, +∞) ✓ validate(1, -∞, 5) 1 is in (-∞, 5) ✓ validate(null) → true validate(null) → true return true validate(7, 5, +∞) 7 is in (5, +∞) ✓ validate(6, 5, 7) 6 is in (5, 7) ✓ return true validate(8, 7, +∞) 8 is in (7, +∞) ✓ return true return true return true Answer: VALID BST ✓ Now consider an INVALID tree: 5 / \ 1 4 ← 4 < 5, but it's in the RIGHT subtree! / \ 3 6 validate(4, 5, +∞) 4 is NOT in (5, +∞) ✗ → return false Key: We don't just check parent-child. The range (5, +∞) ensures that EVERYTHING in the right subtree is > 5, catching the violation.
Kth Smallest (Early-Stop Inorder) — Step by Step
Tree: k = 3 5 / \ 3 6 / \ 2 4 / 1 Inorder traversal (left → node → right): inorder(5) inorder(3) inorder(2) inorder(1) inorder(null) → return count = 1, val = 1 (1st smallest) inorder(null) → return count = 2, val = 2 (2nd smallest) inorder(null) → return count = 3, val = 3 (3rd smallest) ← FOUND! Stop here. return immediately (count >= k) Answer: 3 We visited only 3 nodes (1, 2, 3) out of 6. Nodes 4, 5, 6 were never visited — early stop saved half the work. Key: Inorder visits BST nodes in sorted order. Count during traversal and stop at k. Don't visit the rest.
LCA in BST (Split Point) — Step by Step
Tree: Find LCA of p=2 and q=8 6 / \ 2 8 / \ / \ 0 4 7 9 / \ 3 5 Start at root = 6: p=2 < 6 and q=8 > 6 → SPLIT! LCA = 6 ✓ Another example: LCA of p=2 and q=4 Start at root = 6: p=2 < 6 and q=4 < 6 → both left, go to node 2 At node 2: p=2 = 2 → SPLIT! (one equals current) LCA = 2 ✓ Another example: LCA of p=3 and q=5 Start at root = 6: p=3 < 6 and q=5 < 6 → both left, go to node 2 At node 2: p=3 > 2 and q=5 > 2 → both right, go to node 4 At node 4: p=3 < 4 and q=5 > 4 → SPLIT! LCA = 4 ✓ Key: In a BST, the LCA is the first node where p and q go to different subtrees (or one of them equals the node). We follow a single path — O(h) time, O(1) space.
Practice Problems
These 7 problems are carefully ordered from easy to hard. Each one teaches a different aspect of BST-based problem solving. Solve them in order.
LC 700. Search in a Binary Search Tree
Why this pattern:
BST search — the foundational BST operation. At each node, compare the target with the current value and go left or right. This is binary search on a tree structure.
Key idea: If target < node.val, go left. If target > node.val, go right. If equal, return the node. Iterative is cleaner than recursive. O(h) time, O(1) space. This is the 'hello world' of BSTs.
LC 98. Validate Binary Search Tree
Why this pattern:
Range validation — pass min/max bounds down the tree. Every node must be within its valid range. Going left tightens the upper bound, going right tightens the lower bound.
Key idea: validate(node, min, max): check node.val is in (min, max), then recurse with tightened bounds. Start with (-Infinity, Infinity). The common mistake is only checking parent-child — you must check against the entire ancestor chain via the range. Alternative: inorder traversal must be strictly increasing.
LC 235. Lowest Common Ancestor of a BST
Why this pattern:
BST split point — the LCA is the first node where p and q diverge to different subtrees. Exploit the BST ordering to follow a single path down the tree.
Key idea: If both p and q are smaller than current, go left. If both are larger, go right. Otherwise, current is the split point — it's the LCA. O(h) time, O(1) space. Much simpler than generic tree LCA because the BST property tells you which direction to go.
LC 230. Kth Smallest Element in a BST
Why this pattern:
Inorder traversal with early stop. Since inorder of BST = sorted order, count nodes during traversal and stop at k. No need to collect all values.
Key idea: Inorder traverse, increment counter at each node. When counter = k, record the value and stop. O(k) time instead of O(n). For the follow-up (frequent calls), augment each node with a left-subtree count for O(h) lookup.
LC 108. Convert Sorted Array to Binary Search Tree
Why this pattern:
Divide and conquer construction. Pick the middle element as root to guarantee balance. Recursively build left subtree from left half, right subtree from right half.
Key idea: build(left, right): mid = (left + right) / 2, create node with nums[mid], recurse on [left, mid-1] and [mid+1, right]. The middle element as root ensures the tree is height-balanced. O(n) time, O(log n) space.
LC 450. Delete Node in a BST
Why this pattern:
BST deletion with three cases: (1) leaf — remove, (2) one child — replace with child, (3) two children — replace with inorder successor (smallest in right subtree), then delete the successor.
Key idea: Search for the node using BST property. Case 3 is the key: find the inorder successor (go right once, then all the way left), copy its value to the current node, then recursively delete the successor (which is Case 1 or 2). O(h) time.
LC 99. Recover Binary Search Tree
Why this pattern:
Inorder traversal to detect violations. In a valid BST, inorder is strictly increasing. Two swapped nodes create exactly one or two 'inversions' (where prev > curr). Find the two violating nodes and swap them back.
Key idea: Track 'prev' during inorder. First violation: first = prev (the larger misplaced node). Second violation: second = curr (the smaller misplaced node). After traversal, swap first.val and second.val. O(n) time, O(h) space. The O(1) space follow-up uses Morris traversal.
Practice strategy
For each problem: (1) Identify which BST property you're exploiting before coding. (2) Ask "Does inorder traversal help here?" (3) After solving, write one sentence: "The BST property helps because [reason]." This builds your pattern recognition muscle.
Common Mistakes
These are the traps that catch people on BST problems. Learn them here so you don't learn them in an interview.
Only checking parent-child in validation
You check if left.val < node.val and right.val > node.val, but miss that a node deep in the left subtree could be larger than an ancestor. Example: in a tree with root 5, left child 3, and 3's right child 7 — 7 > 3 (valid parent-child) but 7 > 5 (invalid BST).
✅Pass min/max bounds down the tree. Every node must satisfy min < node.val < max. Going left tightens max to node.val. Going right tightens min to node.val. This catches violations against ALL ancestors, not just the parent.
Using <= or >= instead of strict < and > in validation
You allow equal values in the BST (node.val <= parent.val on the left). Most LeetCode BST problems define BSTs with strict inequality — no duplicates. Using <= causes false positives.
✅Use strict inequality: left subtree values must be strictly less than node, right subtree values must be strictly greater. Check the problem statement for whether duplicates are allowed. When in doubt, ask the interviewer.
Treating a BST problem like a generic tree problem
You use generic DFS/BFS that visits all nodes when the BST property lets you prune. For example, searching for a value by traversing the entire tree instead of going left or right based on comparison.
✅Always ask: 'Can I use the BST ordering to skip nodes?' Search is O(h), not O(n). LCA is O(h), not O(n). Kth smallest is O(k), not O(n). The BST property is your pruning tool — use it.
Forgetting the two-children case in deletion
You handle leaf and one-child deletion correctly but panic at the two-children case. You try to rearrange pointers manually and create an invalid BST.
✅For two children: find the inorder successor (smallest in right subtree — go right once, then all the way left). Copy its value to the current node. Then delete the successor from the right subtree (it's a leaf or has one child — easy). This always maintains the BST property.
Assuming BST is always balanced
You assume O(log n) for all BST operations, but a skewed BST (like a linked list) has height n, making operations O(n). Interviewers may ask about this.
✅Always say 'O(h) where h is the height' instead of 'O(log n)'. Then clarify: 'For a balanced BST, h = O(log n). For a skewed BST, h = O(n).' If the interviewer asks how to guarantee balance, mention AVL trees or Red-Black trees.
Not tracking 'prev' correctly in inorder problems
In problems like Validate BST (inorder approach) or Recover BST, you forget to update 'prev' after processing each node, or you initialize it incorrectly, causing missed violations.
✅Initialize prev = -Infinity (or null). After processing each node in inorder, set prev = node.val (or prev = node). The check is: if node.val <= prev, there's a violation. Always update prev AFTER the check, not before.
Interview Strategy
Knowing when and how to exploit the BST property is half the battle. Here's how to present it in an interview setting to maximize your score.
The 5-Step Interview Flow
Clarify: Is It a BST?
'Just to confirm — this is a binary search tree, so left < node < right for every node, correct? And no duplicates?' This is critical. If it's a generic binary tree, BST techniques don't apply. If it IS a BST, you've just unlocked O(h) operations.
State the BST Property You'll Exploit
'Since this is a BST, inorder traversal gives sorted order. So finding the Kth smallest is just counting during inorder.' Or: 'The BST property means I can find the LCA by following a single path — O(h) instead of O(n).' Name the property explicitly.
Mention the Brute Force, Then Optimize
'I could collect all values and sort — O(n log n). But inorder is already sorted — O(n). And with early stopping, I only need O(k).' Show the progression. Interviewers love seeing you optimize step by step.
Code It Clean
Use descriptive names (validate, not helper). Comment the BST invariant. For recursive solutions, clearly state the base case and the recursive case. For iterative solutions, explain what the stack represents.
Analyze with h, Not log n
'Time is O(h) where h is the tree height. For a balanced BST, h = O(log n). For a skewed tree, h = O(n).' This shows you understand the nuance. If asked about guaranteeing O(log n), mention self-balancing trees.
Common Follow-Up Questions
| Follow-Up | How to Handle |
|---|---|
| "What if the BST is skewed?" | Operations become O(n) instead of O(log n). To guarantee O(log n), use a self-balancing BST like AVL or Red-Black tree. Mention that most language standard libraries use Red-Black trees (Java TreeMap, C++ std::map). |
| "Can you do it iteratively?" | Yes — use an explicit stack to simulate recursion. For inorder: push all lefts, pop, process, go right. The BST Iterator pattern works for any inorder-based problem. Iterative avoids stack overflow on deep trees. |
| "What if kthSmallest is called frequently?" | Augment each node with a count of nodes in its left subtree. Then finding the Kth smallest is O(h): if k <= leftCount, go left. If k = leftCount + 1, current is the answer. Otherwise, go right with k -= leftCount + 1. |
| "Can you validate a BST without extra space?" | Yes — Morris traversal does inorder in O(n) time and O(1) space by temporarily modifying tree pointers. It threads the tree so you can traverse without a stack. Mention it as an advanced technique. |
| "What's the difference between BST LCA and generic tree LCA?" | BST LCA is O(h) — follow one path using the ordering property. Generic tree LCA is O(n) — must search both subtrees because there's no ordering to guide you. The BST property eliminates one subtree at each step. |
| "How would you handle duplicates?" | Convention varies: duplicates can go left (left <= node < right) or right (left < node <= right). Clarify with the interviewer. Some problems use a count field on each node instead of duplicate nodes. |
The meta-skill
Interviewers love BST problems because they test whether you can exploit structure. The key sentence to say is: "Because this is a BST, I know that [specific property], which lets me [specific optimization]." For example: "Because this is a BST, inorder traversal is sorted, so I can find the Kth smallest in O(k) instead of O(n log n)." Always connect the BST property to the optimization.
Summary & Cheat Sheet
Pin this section. Review it before mock interviews and contests.
Quick Revision Cheat Sheet
Core property: For every node: left subtree values < node < right subtree values. This single rule makes everything else possible.
Inorder = sorted: Inorder traversal (left → node → right) of a BST visits nodes in ascending order. This is the #1 fact to remember.
Search: Binary search on a tree: compare target with node, go left or right. O(h) time, O(1) space iterative.
Validation: Pass (min, max) range down. Left tightens max, right tightens min. Don't just check parent-child — check against all ancestors.
Kth smallest: Inorder traversal with counter. Stop at count = k. O(k) time. For frequent calls, augment nodes with left-subtree count.
LCA in BST: Follow one path: both left → go left. Both right → go right. Split → that's the LCA. O(h) time, O(1) space.
Delete (3 cases): Leaf → remove. One child → replace with child. Two children → replace with inorder successor, delete successor.
Inorder successor: If node has right child: go right, then all the way left. If not: go up until you find a parent where node is in the left subtree.
Build balanced BST: From sorted array: pick middle as root, recurse on halves. Guarantees O(log n) height.
BST Iterator: Explicit stack: push all lefts. Pop = next(). After pop, push all lefts of right child. Amortized O(1) per call.
Recover BST: Inorder traversal, track prev. First violation: first = prev. Second violation: second = curr. Swap first and second values.
Complexity caveat: Say O(h), not O(log n). Balanced → h = O(log n). Skewed → h = O(n). Self-balancing trees guarantee O(log n).
Mental trigger: Problem says 'BST' → ask 'How does sorted-order property help?' Inorder traversal is almost always the key.
Decision Flowchart
Is the tree explicitly a BST (problem states it)? ├── NO → Use general binary tree techniques (DFS/BFS) └── YES → What does the problem ask? ├── Validate the BST? │ → Template 1: min/max range OR inorder must be increasing ├── Search / Insert / LCA? │ → Template 2: go left or right based on comparison (O(h)) ├── Kth smallest/largest? Min difference? Recover swapped nodes? │ → Template 3: inorder traversal with state ├── Build BST from sorted data? │ → Template 4: pick middle, recurse on halves ├── Delete a node? │ → Three cases: leaf, one child, two children (inorder successor) ├── Iterator / next smallest? │ → Controlled inorder with explicit stack └── Convert BST to/from sorted list? → Inorder traversal to flatten, or reverse to build
BST Operations Quick Reference
| Operation | Time | Space | Key Insight |
|---|---|---|---|
| Search | O(h) | O(1) iter / O(h) rec | Binary search on tree — go left or right |
| Insert | O(h) | O(1) iter / O(h) rec | Search for position, add as leaf |
| Delete | O(h) | O(h) | 3 cases — two-children uses inorder successor |
| Validate | O(n) | O(h) | Must check every node against its valid range |
| Kth Smallest | O(k) | O(h) | Early-stop inorder — count to k |
| LCA | O(h) | O(1) | Split point — first divergence of p and q |
| Inorder | O(n) | O(h) | Visits all nodes in sorted order |
| Build from sorted | O(n) | O(log n) | Middle element = root, recurse on halves |
| Min / Max | O(h) | O(1) | Go all the way left / right |
One last thing
The BST is one of the most elegant data structures in computer science. Its power comes from a single rule — left < node < right — that turns a tree into a sorted, searchable structure. Every BST interview problem is really asking: "Can you see how the sorted-order property simplifies this?" If you can answer that question, you can solve any BST problem. The inorder traversal is your Swiss Army knife — it converts the tree into a sorted sequence, and from there, the solution is usually straightforward.