184. Kth Smallest Element in a BST

Perform a full in-order traversal to collect all values in sorted order, then return the element at index k-1.

Brute Force

An in-order traversal of a BST visits nodes in ascending order. Collect all values into a list, then simply index into position k-1.

This always visits every node even if k is small. Time is O(n) and space is O(n) for storing the full sorted list.

Why it can be improved: We do not need the entire sorted list — we can stop as soon as we have visited k nodes.

import java.util.*;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        return values.get(k - 1);
    }

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

Walk the tree in-order (left, root, right) and count each node visited. The moment the count reaches k, that node's value is the answer — no need to visit the rest.

Mental Model

In a BST, in-order traversal produces a sorted sequence. Instead of collecting all values, keep a counter. Each time you "visit" a node (between its left and right subtree), increment the counter. When counter == k, you have found the kth smallest — return it immediately.

Algorithm Steps

1. Initialize count = 0 and result = None.
2. Define a recursive inorder(node) function: a. If node is None or result is not None, return (base case or already found). b. Recurse left: inorder(node.left). c. Increment count. If count == k, set result = node.val and return. d. Recurse right: inorder(node.right).
3. Call inorder(root) and return result.

Worked Walk-through

Tree (level-order): [5, 3, 6, 2, 4, null, null, 1], k = 3

        5
       / \
      3   6
     / \
    2   4
   /
  1

In-order traversal visits: 1, 2, 3, 4, 5, 6

We stop after visiting only 3 nodes instead of all 6.

Edge Cases

• k = 1: Return the leftmost (smallest) node in the tree.
• k = n: Return the rightmost (largest) node — we must traverse the entire tree.
• Single node tree: k must be 1, return root.val.

Complexity

• Time: O(H + k) where H is the tree height. We descend to the leftmost node (H steps) then visit k nodes. In the worst case (skewed tree, k = n), this is O(n).
• Space: O(H) for the recursion stack. O(log n) for a balanced tree, O(n) for a skewed one.