Kth Smallest Element in a BST

1. Problem & Core Objective

Given a BST and an integer k, return the k-th smallest value (1-indexed).

      3
     / \        k = 1  →  1
    1   4       k = 3  →  3
     \
      2

Constraints: 1 <= k <= n <= 10^4 · 0 <= Node.val <= 10^4

What's actually being tested: knowing that inorder traversal of a BST yields sorted order, and then stopping early rather than materializing the whole sequence. The follow-up — "what if the tree is modified often?" — is the interesting part and expects a structural answer.

2. First-Principles Thought Process

The one fact you need

Inorder traversal visits left subtree, node, right subtree. In a BST, everything in the left subtree is smaller and everything in the right is larger — so inorder emits values in ascending order.

That turns the problem into: take the k-th element of a sorted stream.

Don't build the whole list

The naive version collects all n values into a list and indexes position k−1. That's O(n) time and O(n) space — and it does full work regardless of how small k is.

But inorder produces values one at a time, in order. So you can count as you go and stop at the k-th. For small k that visits far fewer nodes.

How much is saved

Stopping early costs O(h + k): h to descend to the smallest element, then k steps of traversal. With k = 1 on a balanced tree of 10^4 nodes, that's about 14 nodes instead of 10,000.

Worst case k = n, so it's O(n) — no better than the naive version. The gain is real but input-dependent, and it's worth stating honestly rather than claiming a blanket improvement.

The real question is the follow-up

"What if the BST is modified often and you need to find the k-th smallest frequently?"

Then O(h + k) per query is too slow, and the answer is structural: store in each node the size of its subtree. With that, finding the k-th smallest becomes a descent, like binary search.

3. Solution Paths

Approach 1 — Full inorder into a list (brute force)

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

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

• Time O(n) · Space O(n) for the list, plus O(h) stack

Counter-questions on this approach

⭐ "You build n values and read one. What's wasted?"

Everything past position k. Inorder yields values in ascending order one at a time, so once I've seen k of them I have the answer — the remaining n − k are computed and stored for nothing.

With k = 1 on a balanced tree, that's 10,000 values built to return the first.

"Is O(n) space a real problem at n = 10^4?"

Not at this size. The objection is that the early exit is strictly better with no added complexity, and it's what the question is checking for.

"Could you sort instead of using inorder?"

You could collect all values and sort — but that's O(n log n) and throws away the BST property entirely, which is the one thing the problem hands you. Same mistake as using the general LCA in question 7.

Approach 2 — Inorder with an early exit (optimal for a single query)

private int count = 0, answer = 0;

public int kthSmallest(TreeNode root, int k) {
    count = 0;
    inorder(root, k);
    return answer;
}

private void inorder(TreeNode n, int k) {
    if (n == null || count >= k) return;     // stop descending once found

    inorder(n.left, k);
    if (++count == k) { answer = n.val; return; }
    inorder(n.right, k);
}

Or iteratively, which avoids the mutable fields entirely:

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }   // go as far left as possible
        cur = stack.pop();
        if (--k == 0) return cur.val;
        cur = cur.right;
    }
    return -1;    // unreachable given 1 <= k <= n
}

• Time O(h + k) · Space O(h)

Counter-questions on this approach

⭐ "Why is the time O(h + k) and not O(k)?"

Because before emitting anything you must descend to the leftmost node, which is h steps. After that, each subsequent element costs amortized O(1) — the traversal moves through the tree without revisiting nodes.

So it's h to get started plus k to produce the answers.

⭐ "Why do you prefer the iterative version?"

Two reasons. It has no mutable instance state, so it's reentrant and thread-safe. And it returns immediately on finding the answer, whereas the recursive version has to unwind through every pending frame — the count >= k guard prevents further descent but the stack still unwinds.

The iterative version is also the honest expression of "take the k-th element of a stream": the explicit stack is the traversal's state, paused and resumed.

"Explain the inner while (cur != null) loop."

That's the standard iterative inorder: push nodes while walking left, so the stack holds the chain of ancestors whose left subtrees are being explored. Popping gives the next node in inorder — everything smaller has already been emitted. Then move right and repeat.

"What does --k == 0 do?"

Counts down instead of up, so no separate counter is needed. It decrements on each node emitted in sorted order; hitting zero means this is the k-th.

"How much does the early exit actually save?"

It depends on k. With k = 1 and a balanced tree, about 14 nodes instead of 10,000. With k = n, nothing — it's O(n) either way. I'd state that rather than imply a uniform win.

Approach 3 — Augment nodes with subtree sizes (the follow-up answer)

class Node {
    int val, count;           // count = number of nodes in this subtree, including itself
    Node left, right;
}

public int kthSmallest(Node root, int k) {
    Node node = root;
    while (node != null) {
        int leftCount = (node.left == null) ? 0 : node.left.count;

        if (k == leftCount + 1) return node.val;      // this node is the k-th
        if (k <= leftCount) {
            node = node.left;                          // k-th is in the left subtree
        } else {
            k -= leftCount + 1;                        // skip the left subtree AND this node
            node = node.right;
        }
    }
    return -1;
}

• Time O(h) per query · Space O(1), plus O(n) for the stored counts

Counter-questions on this approach

⭐ "Why does this beat O(h + k)?"

Because it never traverses the elements it skips — it jumps over them. Knowing the left subtree holds leftCount nodes tells me in O(1) whether the answer is inside it, is the node itself, or is to the right. That's binary search using the size as the index.

With k = 10^4 on a balanced tree, the traversal version visits 10,000 nodes; this visits about 14.

⭐ "Why k -= leftCount + 1 when going right?"

Because moving into the right subtree skips the entire left subtree (leftCount nodes) and the current node (1 more). Within the right subtree the target is now the (k − leftCount − 1)-th smallest, so k must be rebased to that subtree's local numbering.

Forgetting the + 1 is the classic bug — it's off by exactly the current node, and it produces an answer one position too large.

"What does maintaining count cost?"

Every insert and delete must update the counts along the path from the changed node to the root — O(h) per modification, which is the same order as the insert itself, so it's essentially free. That's the trade: a small constant on writes to make this query O(h) instead of O(h + k).

"Is this over-engineering for the stated problem?"

For a single query, yes — plain inorder is simpler and fast enough. This is the answer to the follow-up, where the tree is modified often and queried often. I'd write the simple version first and offer this when asked.

Comparison

4. Why the Optimal Wins

Against the full list: inorder already produces values in sorted order one at a time, so building all n and reading one discards everything after position k. The early exit costs nothing to write.

Against O(h + k): the augmented version skips rather than walks. Sizes turn the descent into a binary search, making the cost independent of k. That's the same move as question 7 — using stored structure to navigate instead of traverse.

The framing worth keeping:

Inorder on a BST is a sorted stream — so take the k-th element, don't build the list. And if you need it often, store subtree sizes and the k-th becomes a descent instead of a walk.

5. Java Prerequisites

Recursive inorder

inorder(n.left);  visit(n);  inorder(n.right);

Iterative inorder — worth memorizing, it's the basis of several BST problems:

Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
    while (cur != null) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    // visit cur
    cur = cur.right;
}

ArrayDeque as a stack — push/pop/peek. Faster than java.util.Stack, which is synchronized and legacy.

Counting down — if (--k == 0) avoids a second counter variable.

6. Interview Communication Guide

Clarifying questions: Is k 1-indexed (yes)? Is k guaranteed valid (yes, 1 <= k <= n)? Will the tree be modified between queries (this is the whole follow-up — ask it early)? Can there be duplicate values (no, it's a BST)?

The pitch

"The key fact is that inorder traversal of a BST — left, node, right — visits values in ascending order, because everything in the left subtree is smaller and everything in the right is larger. So the problem becomes taking the k-th element of a sorted stream.

The naive version collects all n values and indexes k−1, but that's O(n) space and computes everything past position k for nothing.

Instead I count as I traverse and stop at the k-th. That's O(h + k) — h to descend to the smallest element, then k steps. With k = 1 on a balanced tree of 10,000 nodes that's about 14 visits instead of 10,000. Though I'd note the gain depends on k: at k = n it's still O(n).

I'd write it iteratively with an explicit stack rather than recursively. It returns immediately on the answer instead of unwinding frames, and it avoids mutable instance state.

If the follow-up is 'the tree is modified often and queried often', the answer is structural: store in each node the size of its subtree. Then finding the k-th is a descent — compare k against the left subtree's size to decide whether the answer is left, is this node, or is right, rebasing k when you go right. That's O(h) per query regardless of k, and maintaining the counts costs O(h) per insert or delete, which is the same order as the insert itself."

Edge cases to volunteer:

Name the two chain cases together. They bracket the O(h + k) bound: one pays the full h before emitting anything, the other pays none. It shows you understand where the h term comes from.

7. Follow-Up Questions — Modified Constraints

⭐ "The BST is modified often and you query the k-th smallest often."

Augment each node with its subtree size, as above. Queries become O(h); inserts and deletes pay O(h) to update counts along the path, which they already walk. This is the expected answer and it's worth reaching for unprompted.

⭐ "Find the k-th LARGEST instead."

Reverse inorder — right, node, left — which emits descending order. Or equivalently ask for the (n − k + 1)-th smallest, which needs n. The reverse traversal is cleaner and keeps the same O(h + k).

"Return all elements between lo and hi."

Inorder with pruning: skip the left subtree when node.val <= lo, skip the right when node.val >= hi. That's O(h + m) for m results, and it's the range-query version of the same idea.

"What if the tree weren't a BST?"

Inorder loses its sorted property, so you'd need a different tool: a size-k max-heap over all nodes at O(n log k), or quickselect on the extracted values at O(n) average. Worth naming that the BST property is doing all the work here.

"Find the median of the BST."

The (n+1)/2-th smallest for odd n, or the mean of the two middle elements for even. With subtree sizes it's O(h); without, O(h + n/2).

"What if the tree didn't fit in memory?"

Inorder is naturally streaming — it emits in order with only O(h) state — so you could walk it from disk and stop at k. The augmented version is better still, since it reads only O(h) nodes total rather than O(h + k).