Kth Smallest Element in a BST (LC 230). Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) in the tree.
Naive on a non-BST tree: collect all values into an array, sort, take arr[k-1]. O(n log n).
Naive that uses the BST property poorly: do an in-order traversal collecting all values, return arr[k-1]. Better — O(n) — but we collect everything when we only need k.
The right approach: do an in-order traversal early-terminating as soon as we've visited k nodes. Average case O(h + k); worst case O(n).
def kth_smallest(root, k): stack = [] while root or stack: while root: # go all the way left stack.append(root) root = root.left root = stack.pop() k -= 1 if k == 0: return root.val root = root.right
That's the BST trick: in-order gives you sorted order; combine with early termination for O(h+k). For balanced trees and small k, that's a massive win over collecting everything.
The deeper insight: BSTs aren't a different traversal pattern — they're the same patterns as binary trees, but with the in-order invariant providing extra information. Many problems that look hard on a general tree are easy on a BST.
A BST is a tree whose in-order traversal is sorted. That's the whole property. Everything else follows.
The invariant:
For every node X, max(X.left subtree) < X.val < min(X.right subtree).
From this single property, three super-powers emerge:
O(h) search. When looking for value v, at each node compare with v: if equal, found; if less, go right; if greater, go left. You eliminate half the tree at every step (in a balanced tree).
In-order = sorted. A direct corollary of the invariant. This makes "kth smallest," "kth largest," "median," "in-order successor," and "convert BST to sorted DLL" trivial.
Predecessor/successor in O(h). The successor of node X is the leftmost node in X's right subtree (or, if no right subtree, the nearest ancestor where X is in the left subtree). Predecessor is the mirror. Used in delete operations.
Sorted. Always sorted, for any BST. This is the property that turns "find median," "find rank," and "convert to sorted array" from hard problems into trivial ones.
def search(root, target): if not root or root.val == target: return root if target < root.val: return search(root.left, target) return search(root.right, target)def insert(root, val): if not root: return TreeNode(val) if val < root.val: root.left = insert(root.left, val) else: root.right = insert(root.right, val) return rootdef delete(root, val): if not root: return None if val < root.val: root.left = delete(root.left, val) elif val > root.val: root.right = delete(root.right, val) else: # found the node to delete if not root.left: return root.right if not root.right: return root.left # Two children: replace with in-order successor (leftmost in right subtree) succ = root.right while succ.left: succ = succ.left root.val = succ.val root.right = delete(root.right, succ.val) return root
Three slots:
Decision direction — left or right based on comparison.
Termination — null or match.
Delete's two-child case — replace with successor (or predecessor — either works).
def in_order(root): stack, cur = [], root while cur or stack: while cur: stack.append(cur) cur = cur.left cur = stack.pop() yield cur.val # or process cur = cur.right
The iterative version lets you stop after k yields — used for "kth smallest."
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')): if not root: return True if not (lo < root.val < hi): return False return (is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi))
Pass tighter bounds as we recurse. Don't just check node.left.val < node.val < node.right.val — that's wrong (it allows 3 in the right subtree of 5 even if it's deeper).
Problem. Given the root of a binary tree, determine if it is a valid BST. A valid BST has every left subtree's values strictly less than the node and every right subtree's values strictly greater.
Example:
5 / \ 1 4 ← INVALID (4 should be > 5) / \ 3 6
Why the naive check fails. A natural-but-wrong approach is to check, at each node, that node.left.val < node.val < node.right.val. This is too local. In the example above, every parent-child pair is valid (1 < 5, 3 < 4 < 6, 4 < 5 with 4 to the right of 5 but the right side... wait, 4 IS the right child of 5, and 4 < 5 — that violates the BST property globally because every right-subtree value must be > root, not just the immediate right child).
The fix: carry min/max bounds down the recursion. At each node, ensure its value lies strictly within the bounds inherited from above. When recursing left, the new upper bound is the current value. When recursing right, the new lower bound is the current value.
def is_valid_bst(root) -> bool: def helper(node, lo, hi): if not node: return True if not (lo < node.val < hi): return False return (helper(node.left, lo, node.val) and helper(node.right, node.val, hi)) return helper(root, float('-inf'), float('inf'))
Dry-run on the example:
Call
(lo, hi)
node.val
Check passes?
Recurse
helper(5, -inf, inf)
-inf, inf
5
yes
(1, -inf, 5), (4, 5, inf)
helper(1, -inf, 5)
-inf, 5
1
yes
both null → True
helper(4, 5, inf)
5, inf
4
NO (4 not > 5)
return False
bubbles up → final answer False ✓
Alternative: in-order check. Run an in-order traversal and verify that each value is strictly greater than the previous.
def is_valid_bst_inorder(root): prev = [float('-inf')] def in_order(node): if not node: return True if not in_order(node.left): return False if node.val <= prev[0]: return False prev[0] = node.val return in_order(node.right) return in_order(root)
Both work; min/max bounds are more idiomatic.
Complexity. O(n) time — every node visited once. O(h) recursion depth.
Run in-order; find the two "out of order" pairs; swap them.
def recover_tree(root): first = second = prev = None def in_order(node): nonlocal first, second, prev if not node: return in_order(node.left) if prev and prev.val > node.val: if not first: first = prev second = node prev = node in_order(node.right) in_order(root) first.val, second.val = second.val, first.val
Time: O(h) per single-node operation (search, insert, delete, find predecessor/successor).
For a balanced BST: O(log n).
For a skewed BST (worst case): O(n).
Space: O(h) recursion. Same balanced vs skewed asymmetry.
For all-element operations (in-order traversal, range scan): O(n) time.
Self-balancing BSTs (AVL, Red-Black, Treap, Splay) maintain h = O(log n) automatically. In interviews, you rarely need to implement these — just mention them. In production, std::map, TreeMap, SortedDict are typically Red-Black trees.
Database B-trees / B+-trees. Generalizations of BSTs with higher fan-out, used by every database for indexed lookup.
Filesystem extent trees. ext4, NTFS, btrfs all use B-tree variants to index file blocks.
Standard-library ordered maps.std::map / std::set (C++), TreeMap / TreeSet (Java), SortedDict (Python via sortedcontainers) — all Red-Black trees.
Priority queues with ordered iteration. When you need both heap-like priority and sorted iteration, a balanced BST works (a plain heap doesn't give sorted iteration cheaply).
Time-series indexes. Storing events by timestamp for fast range queries — sorted-set or interval-tree.
# Searchdef search(root, t): while root and root.val != t: root = root.left if t < root.val else root.right return root# In-order iterator (lazy, can early-stop)stack, cur = [], rootwhile cur or stack: while cur: stack.append(cur); cur = cur.left cur = stack.pop() yield cur.val # this gives sorted order cur = cur.right# Validatedef valid(node, lo=-inf, hi=inf): if not node: return True if not (lo < node.val < hi): return False return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)# LCAwhile root: if p.val < root.val > q.val: root = root.left elif p.val > root.val < q.val: root = root.right else: return root
Triggers: BST, sorted iteration, range queries, "kth smallest in BST". Complexity: O(h) per op.
