Trees
Binary Search Tree Fundamentals
A binary tree with one additional constraint — the BST property: for every node, all values in its left subtree are strictly less and all values in its right subtree are strictly greater. This ordering invariant transforms O(n) linear search into O(log n) binary search on a linked structure.
Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation
What is Binary Search Tree?
The ordering constraint that separates a binary search tree from a general binary tree is a single invariant applied recursively: every node's value is strictly greater than all values in its left subtree and strictly less than all values in its right subtree, making the entire structure a sorted collection navigable by comparison alone. That invariant buys logarithmic elimination — every comparison at a node discards an entire subtree, halving the remaining candidates at each step and reducing search from O(n) linear scan to O(log n) binary search without requiring the data to be stored in a contiguous array. Beyond search, the ordering produces a remarkable side effect: inorder traversal of a BST visits nodes in ascending sorted order, making it the only tree structure where a standard traversal yields sorted output as a natural byproduct. The hidden danger is that a BST is only O(log n) when balanced — inserting already-sorted data produces a degenerate tree of height n−1 that degrades every operation to O(n), which is why self-balancing variants like AVL and Red-Black trees exist. In Java, TreeMap and TreeSet use red-black trees — a self-balancing BST — internally, giving O(log n) put, get, contains, floor, ceiling, and range operations that make sorted collections practical at scale.
Analogy: A dictionary where every page is a decision point — the word you seek is either on this page, in the left half (alphabetically before), or in the right half (alphabetically after). At each page you eliminate half the remaining book. That is a binary search tree: every node is a comparison that routes you left or right, and the ordering constraint guarantees you are always moving toward your target — never backward, never sideways. A sorted dictionary works because of its ordering invariant; a BST works for exactly the same reason.
02
Section Two · Mental Model
How It Thinks
Every comparison eliminates an entire subtree
▶
Search costs O(log n) on a balanced BST — the same binary search as on a sorted array, but on a linked structure
The BST property holds at every node, not just the root
▶
Validation cannot check only the root's children — it must propagate min/max bounds through the entire tree top-down
Inorder traversal visits left subtree before root before right
▶
Inorder traversal of a BST always yields sorted ascending output — the sorted array view of the BST is free and always up to date
Insertion always adds a new leaf — never restructures existing nodes
▶
Insert follows the search path until null and places the node there — no rotations, no rebalancing in a plain BST
Inserting already-sorted data appends to one side only
▶
Sorted insertion creates a degenerate right-skewed chain — height becomes O(n) and all operations degrade to O(n)
Deletion with two children cannot remove the node directly
▶
The node must be replaced with its inorder successor (leftmost node in the right subtree) to preserve the BST property
03
Section Three · BST Property
The BST Property — The Ordering Invariant
The BST property is the single rule that makes a binary tree searchable: for every node N, every value in the left subtree of N is strictly less than N's value, and every value in the right subtree of N is strictly greater — this invariant must hold not just for direct children but for every node in both subtrees. The most common interview mistake is checking only direct children (left.val < node.val < right.val) and missing violations where a node's value is correct relative to its parent but wrong relative to a distant ancestor — the classic "subtree violation" that requires propagating bounds through the entire tree.
Valid BST vs Invalid BST — ancestor violation
Validating the BST Property
Pseudocode
function isValidBST(node, min, max):
if node is null: return true if node.val <= min or node.val >= max:
return false // value outside allowed range return isValidBST(node.left, min, node.val) // tighten max and isValidBST(node.right, node.val, max) // tighten min // O(n) — every node checked once // Initial call: isValidBST(root, -∞, +∞)
Validation — bound propagation on the invalid BST
Check min/max bounds, not parent comparison:
- The naive check (node.left.val < node.val < node.right.val) fails on ancestor violations — a node can satisfy its parent's constraint while violating a grandparent's.
- The correct approach passes inherited bounds [min, max] top-down and rejects any node whose value falls outside its allowed range.
- This is the standard O(n) single-pass BST validation.
04
Section Four · Operations
Core Operations
Search
Compares the target value with the current node and recurses into the left subtree if smaller, the right subtree if larger, or returns the current node if equal — eliminating one subtree at every step.
Pseudocode
function search(node, target):
if node is null: return null // not found if target == node.val: return node
if target < node.val:
return search(node.left, target) // go left else:
return search(node.right, target) // go right // O(h): O(log n) balanced, O(n) degenerate
Search — finding value 6 in the BST
Search on a BST is binary search — not linear scan:
- Each comparison eliminates an entire subtree.
- On a balanced tree of 1,000,000 nodes, search visits at most 20 nodes (log₂ 1,000,000 ≈ 20).
- The iterative version (while loop, no recursion) is preferred in practice — it avoids call stack overhead and is easier to reason about for very deep trees.
Insert
Follows the search path to find where the new value belongs — the position where search would return null — and places a new leaf node there, preserving the BST property without restructuring.
Pseudocode
function insert(node, val):
if node is null:
return new TreeNode(val) // insert here as a new leaf if val < node.val:
node.left = insert(node.left, val)
else if val > node.val:
node.right = insert(node.right, val)
// val == node.val: duplicate — ignore (or handle per requirements) return node // O(h): O(log n) balanced, O(n) degenerate
Insert — adding value 5 to the BST
Insert always creates a new leaf — no restructuring:
- Unlike arrays (which require shifting) or balanced BSTs (which require rotations), a plain BST insert always adds a new leaf at the exact position where the search terminated.
- The return-node pattern (returning node at each recursive call) cleanly handles the parent pointer update without a separate parent reference.
Min / Max / Floor / Ceiling
BST structure makes extremes and neighbors O(h) — min is the leftmost node, max is the rightmost node, floor is the largest value ≤ target, ceiling is the smallest value ≥ target.
Pseudocode
function findMin(node):
while node.left != null: node = node.left
return node // leftmost node function findMax(node):
while node.right != null: node = node.right
return node // rightmost node function floor(node, target):
if node is null: return null if node.val == target: return node
if node.val > target:
return floor(node.left, target) // must go left // node.val < target — this node is a candidate, but right might be closer
rightFloor = floor(node.right, target)
return rightFloor if rightFloor != null else node
// O(h) function ceiling(node, target):
if node is null: return null if node.val == target: return node
if node.val < target:
return ceiling(node.right, target) // must go right
leftCeiling = ceiling(node.left, target)
return leftCeiling if leftCeiling != null else node
// O(h)
Floor and ceiling exploit BST ordering — O(h) not O(n):
- On a sorted array, floor and ceiling require binary search — O(log n).
- On a BST, the same logic works by following left or right pointers: any node smaller than the target is a floor candidate, but the right subtree might have a closer candidate.
- Java's TreeMap exposes this via floorKey(key) and ceilingKey(key), both O(log n).
Complexity Reference
| Operation | Balanced BST | Degenerate BST | Notes |
|---|---|---|---|
| Search | O(log n) | O(n) | Follows one path root-to-leaf |
| Insert | O(log n) | O(n) | Always adds new leaf |
| Delete | O(log n) | O(n) | 3 cases; see Section 7 |
| Find Min/Max | O(log n) | O(n) | Go left/right until null |
| Floor/Ceiling | O(log n) | O(n) | BST-ordering exploitation |
| Inorder | O(n) | O(n) | Must visit all nodes |
| Validate BST | O(n) | O(n) | Must check all nodes |
05
Section Five · Traversals
Traversals on a BST — Why Inorder Is Special
All four traversal orders from the Binary Tree page work identically on a BST — the BST property does not change how traversal works, but it fundamentally changes what inorder traversal produces: unlike a general binary tree where inorder output is arbitrary, inorder traversal of a BST always yields elements in ascending sorted order. This sorted-output guarantee is not incidental — it is a direct consequence of the BST invariant (left < root < right at every node) and makes inorder traversal the solution to any problem requiring sorted extraction, kth smallest, or in-place BST sorting.
Inorder traversal — sorted output from a BST
BST Traversal Use Cases
| Traversal | Produces | Common BST Use Case |
|---|---|---|
| Inorder | Sorted ascending output | Kth smallest, sorted iteration, BST sort |
| Preorder | Root-first serialisation | Reconstruct BST from array (O(n) with BST property) |
| Postorder | Children-first aggregation | Delete all nodes, size/height computation |
| Level-Order | Level-by-level | Minimum depth, BST level sums |
Kth Smallest Element
Returns the kth smallest value in the BST — the kth node visited in inorder traversal.
Pseudocode
function kthSmallest(node, k):
// Iterative inorder — stop at kth visit
stack = empty stack
count = 0
curr = node
while curr != null or stack not empty:
while curr != null:
push(stack, curr)
curr = curr.left
curr = pop(stack)
count++
if count == k: return curr.val // found kth smallest
curr = curr.right
// O(h + k) — not O(n)
Kth smallest stops early — O(h + k) not O(n):
- The iterative inorder approach stops as soon as the kth node is visited — it does not traverse the entire tree.
- Cost is O(h) to reach the leftmost node plus O(k) to count up to k — significantly faster than full traversal when k is small.
- The recursive version requires extra state (a counter passed by reference or a class field) to stop early — the iterative version is cleaner for this problem.
06
Section Six · Variants
BST Variants — When Balance Matters
A plain BST offers O(log n) operations only when balanced — the insertion order of the data determines the tree's shape, and inserting sorted data degrades every operation to O(n) by creating a degenerate chain; self-balancing BST variants solve this by performing rotations after insert and delete to maintain a height bound of O(log n) regardless of insertion order. For interviews, understanding that AVL trees and Red-Black trees are BSTs with automatic rebalancing is sufficient — you will not be asked to implement rotations, but you will be asked why Java's TreeMap is O(log n) for all inputs while a plain BST can degrade to O(n).
Balanced BST vs Degenerate BST — same values, different insertion order
BST Variants Comparison
| Variant | Balance Guarantee | Height | Rotations | Java Class |
|---|---|---|---|---|
| Plain BST | None | O(n) worst | None | Custom TreeNode |
| AVL Tree | |h(L)−h(R)| ≤ 1 | O(log n) strict | Yes (LL,RR,LR,RL) | None built-in |
| Red-Black Tree ← Java | Longest path ≤ 2× shortest | O(log n) | Yes (color flip + rotation) | TreeMap / TreeSet |
| Splay Tree | Amortised O(log n) | O(n) worst | Yes (splay) | None built-in |
| Treap | Expected O(log n) | O(log n) expected | Randomised | None built-in |
AVL vs Red-Black — know the trade-off conceptually:
- AVL trees are more strictly balanced (|h(L) − h(R)| ≤ 1 at every node) which makes lookups slightly faster — at the cost of more rotations on insert and delete.
- Red-Black trees are less strictly balanced but require fewer rotations, making insert and delete faster in practice.
- Java chose Red-Black for TreeMap and TreeSet because real-world workloads involve more writes than reads in sorted collections.
07
Section Seven · Delete
The Delete Problem — Three Cases
Deletion is the hardest BST operation because removing a node with two children cannot eliminate it directly — the tree must be restructured to maintain the BST property, and the restructuring strategy is non-obvious until you understand why the inorder successor is the correct replacement. The three cases — deleting a leaf, deleting a node with one child, and deleting a node with two children — must be handled separately, and only the third case requires any structural reasoning. The inorder successor (the leftmost node in the right subtree) is always the correct replacement for a two-child deletion because it is the smallest value larger than the deleted node, maintaining the BST property for all remaining nodes in both subtrees.
Delete — three cases side by side
Delete Implementation
Java
// BST Delete — handles all 3 cases O(h) TreeNode delete(TreeNode node, int val) {
if (node == null) return null; // not found if (val < node.val) {
node.left = delete(node.left, val); // go left
} else if (val > node.val) {
node.right = delete(node.right, val); // go right
} else {
// FOUND the node to delete — handle 3 cases: // Case 1: leaf node if (node.left == null && node.right == null) return null;
// Case 2: one child — return the non-null child if (node.left == null) return node.right;
if (node.right == null) return node.left;
// Case 3: two children — find inorder successor TreeNode successor = findMin(node.right); // leftmost in right subtree
node.val = successor.val; // copy successor's value
node.right = delete(node.right, successor.val); // delete successor
}
return node;
}
// Helper: find leftmost node (minimum value) TreeNode findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
Why the inorder successor — and not the predecessor?:
- Both the inorder successor (smallest value in the right subtree) and the inorder predecessor (largest value in the left subtree) are valid replacements for a two-child deletion — both maintain the BST property.
- The convention of using the inorder successor is a convention; some implementations use the predecessor.
- What matters is understanding why either choice works: the replacement must be the value closest to the deleted node in sorted order.
Common Mistake: Confusing "delete the inorder successor node" with "restructure the tree." After copying the successor's value into the deleted node's position, the successor must be deleted from the right subtree — and that deletion is itself a recursive delete call. The successor has at most one child (no left child, by definition of leftmost), so this recursive call always reduces to Case 1 or Case 2 — it never recurses into Case 3 again.
08
Section Eight · Implementation
Build It Once
Build this from scratch once — it makes the mechanics concrete. In any real project or interview, reach for the built-in (Section 09).
Java — BST core mechanics
// BST operations follow the search path — go left if smaller, // right if larger. All three operations here are O(h): O(log n) // balanced, O(n) degenerate. // Search — iterative (preferred over recursive) O(h) TreeNode search(TreeNode node, int target) {
while (node != null && node.val != target)
node = (target < node.val) ? node.left : node.right;
return node; // null if not found, node if found
}
// Insert — recursive with return-node pattern O(h) TreeNode insert(TreeNode node, int val) {
if (node == null) return new TreeNode(val);
if (val < node.val) node.left = insert(node.left, val);
else if (val > node.val) node.right = insert(node.right, val);
return node; // return-node pattern rewires parent pointers
}
// Validate BST — min/max bounds propagation O(n) boolean isValidBST(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return isValidBST(node.left, min, node.val) // tighten max
&& isValidBST(node.right, node.val, max); // tighten min
}
// Initial call: isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)
Binary Search Tree — Full Implementation
Java — Complete Binary Search Tree implementation
import java.util.*;
public class BinarySearchTree {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
TreeNode root;
// ── Insert (iterative) ──────────────────────────── O(h) void insert(int val) {
if (root == null) { root = new TreeNode(val); return; }
TreeNode curr = root;
while (true) {
if (val < curr.val) {
if (curr.left == null) { curr.left = new TreeNode(val); return; }
curr = curr.left;
} else if (val > curr.val) {
if (curr.right == null) { curr.right = new TreeNode(val); return; }
curr = curr.right;
} else return; // duplicate — skip
}
}
// ── Search (iterative) ─────────────────────────── O(h) TreeNode search(int target) {
TreeNode curr = root;
while (curr != null && curr.val != target)
curr = (target < curr.val) ? curr.left : curr.right;
return curr;
}
// ── Delete (recursive, 3 cases) ───────────────── O(h) void delete(int val) { root = deleteNode(root, val); }
private TreeNode deleteNode(TreeNode node, int val) {
if (node == null) return null;
if (val < node.val) node.left = deleteNode(node.left, val);
else if (val > node.val) node.right = deleteNode(node.right, val);
else {
if (node.left == null) return node.right; // case 1 & 2 if (node.right == null) return node.left; // case 2 TreeNode succ = findMin(node.right); // case 3
node.val = succ.val;
node.right = deleteNode(node.right, succ.val);
}
return node;
}
// ── Inorder → sorted list ──────────────────────── O(n) List<Integer> inorder() {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> list) {
if (node == null) return;
inorderHelper(node.left, list);
list.add(node.val);
inorderHelper(node.right, list);
}
// ── Validate BST ──────────────────────────────── O(n) boolean isValidBST() { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); }
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val)
&& validate(node.right, node.val, max);
}
// ── Find Min / Max ────────────────────────────── O(h) TreeNode findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
TreeNode findMax(TreeNode node) {
while (node.right != null) node = node.right;
return node;
}
// ── Floor (largest value ≤ target) ────────────── O(h) Integer floor(int target) {
TreeNode curr = root;
Integer result = null;
while (curr != null) {
if (curr.val == target) return curr.val;
if (curr.val < target) { result = curr.val; curr = curr.right; }
else curr = curr.left;
}
return result;
}
// ── Ceiling (smallest value ≥ target) ─────────── O(h) Integer ceiling(int target) {
TreeNode curr = root;
Integer result = null;
while (curr != null) {
if (curr.val == target) return curr.val;
if (curr.val > target) { result = curr.val; curr = curr.left; }
else curr = curr.right;
}
return result;
}
// ── Kth Smallest (iterative inorder) ─────────── O(h + k) int kthSmallest(int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
int count = 0;
while (curr != null || !stack.isEmpty()) {
while (curr != null) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
if (++count == k) return curr.val;
curr = curr.right;
}
throw new IllegalArgumentException("k out of range");
}
// ── Height ────────────────────────────────────── O(n) int height() { return h(root); }
private int h(TreeNode n) {
if (n == null) return -1;
return 1 + Math.max(h(n.left), h(n.right));
}
// ── Main ───────────────────────────────────────────── public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// 1. Build BST by inserting values for (int v : new int[]{8,3,10,1,6,9,14}) bst.insert(v);
System.out.println("Inorder: " + bst.inorder());
// → [1, 3, 6, 8, 9, 10, 14] (sorted!) // 2. Search System.out.println("Search 6: " + (bst.search(6) != null)); // true System.out.println("Search 7: " + (bst.search(7) != null)); // false // 3. Delete 3 (two-child case)
bst.delete(3);
System.out.println("After delete 3: " + bst.inorder());
// → [1, 6, 8, 9, 10, 14] // 4. Validate BST System.out.println("Valid BST: " + bst.isValidBST()); // true // 5. Kth smallest: 3rd smallest in remaining tree System.out.println("3rd smallest: " + bst.kthSmallest(3)); // 8
}
}
Python — Binary Search Tree implementation
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# ── Search (iterative) ──────────────────────── O(h) def search(node, target):
while node and node.val != target:
node = node.left if target < node.val else node.right
return node
# ── Insert (recursive) ──────────────────────── O(h) def insert(node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = insert(node.left, val)
elif val > node.val:
node.right = insert(node.right, val)
return node
# ── Delete (recursive, 3 cases) ─────────────── O(h) def delete(node, val):
if not node:
return None if val < node.val:
node.left = delete(node.left, val)
elif val > node.val:
node.right = delete(node.right, val)
else:
if not node.left: return node.right # case 1 & 2 if not node.right: return node.left # case 2
succ = find_min(node.right) # case 3
node.val = succ.val
node.right = delete(node.right, succ.val)
return node
# ── Inorder → sorted list ──────────────────── O(n) def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
# ── Validate BST ──────────────────────────── O(n) def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
if not node:
return True if node.val <= lo or node.val >= hi:
return False return is_valid_bst(node.left, lo, node.val) \
and is_valid_bst(node.right, node.val, hi)
# ── Find Min / Max ────────────────────────── O(h) def find_min(node):
while node.left:
node = node.left
return node
def find_max(node):
while node.right:
node = node.right
return node
# ── Floor (largest value ≤ target) ────────── O(h) def floor_val(node, target):
result = None while node:
if node.val == target:
return node.val
if node.val < target:
result = node.val
node = node.right
else:
node = node.left
return result
# ── Ceiling (smallest value ≥ target) ────── O(h) def ceiling_val(node, target):
result = None while node:
if node.val == target:
return node.val
if node.val > target:
result = node.val
node = node.left
else:
node = node.right
return result
# ── Kth Smallest (iterative inorder) ─────── O(h + k) def kth_smallest(node, k):
stack, curr, count = [], node, 0 while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
count += 1 if count == k:
return curr.val
curr = curr.right
09
Section Nine · Java Reference
Use It In Java
IN JAVA — TreeMap and TreeSet are BSTs
TreeMap<K,V> — BST operations on a sorted map
TreeMap<Integer, String> map = new TreeMap<>();
// Standard operations — O(log n)
map.put(8, "eight");
map.put(3, "three");
map.put(10, "ten");
// BST-specific navigation — the BST advantage in Java
map.floorKey(7); // → 3 (largest key ≤ 7)
map.ceilingKey(7); // → 8 (smallest key ≥ 7)
map.higherKey(8); // → 10 (strictly greater than 8)
map.lowerKey(8); // → 3 (strictly less than 8)
map.firstKey(); // → 3 (minimum — leftmost node)
map.lastKey(); // → 10 (maximum — rightmost node) // Sorted iteration — inorder traversal for (Map.Entry<Integer,String> e : map.entrySet()) {
// visits entries in ascending key order — BST inorder
}
// Range view — O(log n) to obtain, O(k) to iterate
map.subMap(3, true, 10, false); // keys in [3, 10)
TreeSet<E> — BST operations on a sorted set
TreeSet<Integer> set = new TreeSet<>();
set.add(8); set.add(3); set.add(10); set.add(1);
set.floor(7); // → 3 (largest element ≤ 7)
set.ceiling(7); // → 8 (smallest element ≥ 7)
set.higher(8); // → 10 (strictly greater)
set.lower(8); // → 3 (strictly less)
set.first(); // → 1 (minimum)
set.last(); // → 10 (maximum) // Sorted iteration for (int val : set) { /* ascending order */ }
When to use what
| Need | Use | BST Operation Under the Hood |
|---|---|---|
| Sorted key→value storage | TreeMap<K,V> | Red-Black BST with O(log n) nav |
| Sorted unique values | TreeSet<E> | Red-Black BST (same as TreeMap's keyset) |
| Floor/ceiling/range queries | TreeMap or TreeSet | BST left/right traversal |
| Custom BST / structural problems | Custom TreeNode | Build from scratch for interviews |
| Priority ordering (not sorted) | PriorityQueue | Binary min-heap — not a BST |
⚠ Gotcha: TreeMap and TreeSet maintain sorted order and provide BST-like navigation, but they expose no node-level API — you cannot access parent pointers, left/right children, or perform rotations. For interview problems requiring structural tree manipulation (LCA, serialize/deserialize, validate BST), always build a custom TreeNode from scratch.
⚠ Gotcha: Use
long (not int) as bounds when validating a BST in Java — node values can be Integer.MIN_VALUE or Integer.MAX_VALUE, and passing int min/max bounds causes overflow. Initialize: isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE).
10
Section Ten · Practice
Problems To Solve
BST problems split into two categories: structural problems that require understanding the BST property itself (validate BST, insert, delete, lowest common ancestor), where the ordering invariant drives every decision, and sorted-output problems that exploit inorder traversal (kth smallest, convert sorted array to BST, recover BST). Before writing code on any BST problem, confirm whether the BST property actually helps — some problems on BST nodes are solved exactly like general binary tree problems (height, depth, symmetry), while others are O(log n) precisely because the ordering allows elimination of an entire subtree at every comparison.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | dfs | Validate Binary Search Tree — LC 98 | Pass long min and max bounds top-down — not int, to avoid overflow with Integer.MIN_VALUE/MAX_VALUE inputs. A node is invalid if node.val ≤ min or node.val ≥ max. |
| Easy | dfs | Search in a Binary Search Tree — LC 700 | Prefer the iterative version — while node != null, go left if target < node.val, go right if larger, return node if equal. No recursion overhead, no call stack. |
| Medium | dfs | Insert into a Binary Search Tree — LC 701 | Recurse left or right to the null position, return a new TreeNode(val). The return-node pattern updates parent pointers without a separate parent reference. |
| Medium | dfs | Delete Node in a BST — LC 450 | Three cases in order: (1) leaf → return null, (2) one child → return that child, (3) two children → copy inorder successor value then recursively delete successor from right subtree. |
| Medium | dfs | Kth Smallest Element in a BST — LC 230 | Iterative inorder with an early exit — decrement a counter on each visit, return when counter reaches zero. Cost is O(h + k), not O(n). Recursive version needs a class-level or array counter to enable early exit. |
| Medium | dfs | Lowest Common Ancestor of a BST — LC 235 | Exploit BST ordering: if both p and q are less than node, go left; if both greater, go right; otherwise node is the LCA. O(log n) on balanced BST — faster than general binary tree LCA. |
Interview Pattern:
- For BST problems, always ask first: does this problem need to exploit the BST ordering property, or is it a binary tree problem that happens to be on a BST?
- If the ordering matters (search, insert, delete, LCA, floor/ceiling), the BST property drives every decision.
- If the ordering does not matter (height, balance check, level-order), solve it exactly as you would a general binary tree.
- Conflating the two approaches leads to O(n) solutions for problems that should be O(log n).