Kth Smallest Element in a BST (LC 230)

Pattern: BST Inorder Traversal
Difficulty: Medium
Key Concept: Inorder traversal of a BST visits nodes in sorted ascending order; the kth visited node is the kth smallest.

Problem Statement

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) in the tree.

Input: BST root, integer k (valid).
Output: int — kth smallest value.

Example

      3
     / \
    1   4
     \
      2

k = 1 → 1; inorder: 1,2,3,4.

---

1. Algorithm & Pseudocode

Brute force

1. Collect all values via any traversal into a list, sort the list, return index k-1 — O(n log n) time, O(n) space.
2. Or: inorder full list then pick — O(n) time (still visits all nodes even if k is small).

Pseudocode

vals = []
inorder(root, vals)   // O(n)
sort(vals)            // O(n log n) if not BST property used
return vals[k-1]

Optimal

1. Iterative inorder with stack: go left as far as possible, pop (this is the next smallest), decrement k; when k == 0, return value — O(h + k) time, O(h) space.
2. Follow-up: augment tree with subtree sizes → O(h) per query after O(n) preprocessing.

Pseudocode (early stop inorder)

stack = empty
cur = root
while true:
    while cur != null:
        push cur; cur = cur.left
    cur = pop
    k--
    if k == 0: return cur.val
    cur = cur.right

---

2. Step-by-Step Analysis (Beginner-Friendly)

• BST property: left < root < right guarantees sorted inorder.
• Why not always collect full list: For large trees and small k, you stop after k pops — saves time.
• Why iterative stack: Same logic as recursion but you control when to stop without unwinding entire recursion.

---

3. The Dry Run

Tree (k = 2)

      3
     / \
    1   4
     \
      2

Inorder order: 1 → 2 → 3 → 4

Step	Action	Stack (bottom→top)	cur after	k after pop	Popped value
1	go left from 3	[3]	at 1	—	—
2	go left from 1	[3,1]	null	—	—
3	pop 1	[3]	—	1	1
4	go right from 1 → 2	[3,2]	null	—	—
5	pop 2	[3]	—	0	return 2

ASCII (inorder visit order numbered)

      3  (3rd)
     / \
  (1)1   4 (4th)
     \
      2 (2nd)

---

4. Java Solution

Brute Force

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class SolutionBrute {
    // Time: O(n log n) if sort; O(n) if only inorder on BST
    // Space: O(n)
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        Collections.sort(vals); // redundant if guaranteed BST; shows brute mindset
        return vals.get(k - 1);
    }

    private void inorder(TreeNode n, List<Integer> vals) {
        if (n == null) return;
        inorder(n.left, vals);
        vals.add(n.val);
        inorder(n.right, vals);
    }
}

Optimal

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    // Time: O(h + k), Space: O(h)
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;
        while (true) {
            while (cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            cur = st.pop();
            if (--k == 0) return cur.val;
            cur = cur.right;
        }
    }
}

Recursive early stop (field for count)

class SolutionRecursive {
    private int k;
    private Integer ans;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode n) {
        if (n == null || ans != null) return;
        dfs(n.left);
        if (--k == 0) ans = n.val;
        dfs(n.right);
    }
}

---

5. The “Java vs. Others” Edge

• ArrayDeque as stack: push/pop are clear; Deque<TreeNode> is preferred over legacy Stack.
• Integer ans nullable box lets you short-circuit recursion when found.
• For many queries on the same tree, LeetCode follow-up: persist subtree counts in a wrapper class or use persistent order-statistic tree (outside standard library).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute sort	O(n log n)	O(n)	Ignores BST; still works if tree is BST
Full inorder list	O(n)	O(n)	Visits every node
Early-stop inorder	O(h + k)	O(h)	Stops after k pops; best when k ≪ n