Kth Smallest Element in BST LeetCode 230

LeetCode 230 — Kth Smallest Element in a BST — gives you the root of a binary search tree and an integer k. Return the k-th smallest value (1-indexed) among all nodes in the BST.

The fundamental property of a BST is that an inorder traversal (left, root, right) visits nodes in ascending order. The k-th node visited during inorder traversal is the k-th smallest element. No sorting needed.

Two implementations: recursive inorder (simple but traverses the entire tree) and iterative inorder with a stack (can stop as soon as the k-th element is found). The iterative approach is preferred for its early termination capability.

In a BST, every node's left subtree contains only smaller values, and the right subtree contains only larger values. Inorder traversal recursively visits left subtree, then the current node, then the right subtree.

This left-root-right order produces values in ascending sequence. For example, a BST with values [1, 2, 3, 4, 5, 6] produces inorder: 1, 2, 3, 4, 5, 6. The k-th value in this sequence is the k-th smallest.

The connection between BSTs and sorted order is the core insight. Any BST problem that asks about rank, order, or position can be solved by leveraging inorder traversal.

Initialize an empty stack and a pointer curr = root. While the stack is non-empty or curr is not null: push all left children of curr onto the stack (go as far left as possible). Pop the top node — this is the next smallest element. Decrement k. If k reaches 0, return the node's value.

If k is not yet 0, move curr to the popped node's right child and repeat. The right subtree contains the next larger values. The stack stores ancestors waiting to be processed after their left subtrees.

This iterative approach visits exactly H + k nodes in the worst case: H to reach the leftmost node (going down the left spine), then k to traverse to the k-th element. It stops immediately without processing the remaining n - k nodes.

Consider BST: 5 with left child 3 (left: 2 with left: 1, right: 4) and right child 6. k = 3. Stack: []. curr = 5. Push left: 5, 3, 2, 1. Stack: [5, 3, 2, 1]. curr = null.

Pop 1 (k=3→2). Right child is null. Pop 2 (k=2→1). Right child is null. Pop 3 (k=1→0). Return 3! The 3rd smallest element is 3. We only visited 3 nodes out of 6 — the iterative approach saved work.

If k were 5, we would continue: after popping 3, move to right child 4. Push 4. Pop 4 (k=2→1... wait, let me recount). After returning 3 at k=0, we stop. For k=5, we would continue through 4, 5, then into the right subtree to 6.

Python iterative: stack = []. curr = root. While stack or curr: while curr: stack.append(curr); curr = curr.left. curr = stack.pop(). k -= 1. If k == 0: return curr.val. curr = curr.right.

Python recursive: result = []. def inorder(node): if not node or len(result) >= k: return. inorder(node.left). result.append(node.val). inorder(node.right). inorder(root). return result[k-1]. Simpler but visits all nodes.

Java iterative: Deque<TreeNode> stack = new ArrayDeque<>(). TreeNode curr = root. Same while loop with push-left, pop, decrement k, check, move right. Return value when k reaches 0.

Iterative: O(H + k) time where H is the tree height. We traverse H nodes to reach the leftmost, then k nodes to reach the answer. For a balanced BST, H = log n, so time is O(log n + k). For a skewed BST, H = n.

Space: O(H) for the stack. The stack holds at most H nodes (the height of the tree). For a balanced BST, this is O(log n). For a skewed tree, O(n).

The follow-up asks: what if the BST is modified often (insert/delete) and kthSmallest is called frequently? Augment each node with a count of nodes in its left subtree. Then kthSmallest becomes O(H) without traversal, and updates are O(H) per modification.

Validate Binary Search Tree (LeetCode 98) uses inorder traversal to verify sorted order. Kth Smallest uses the same traversal to find a specific rank. Both leverage the BST inorder property.

Binary Search Tree Iterator (LeetCode 173) implements a controlled inorder traversal with next() and hasNext(). It uses the same iterative stack approach as Kth Smallest but wraps it in an iterator interface.

Inorder Successor in BST (LeetCode 285) finds the next node in inorder sequence. Combined with Kth Smallest and BST Iterator, these three problems form the complete BST traversal toolkit.