A ranked catalog stores SKU prices in a BST so “everything under $X” stays a cheap range walk. Finance wants the kth cheapest live SKU for a value-band report — 1-indexed, so k = 1 is the cheapest. The intern version dumped every inorder key into a list, then returned list.get(k - 1). A dozen SKUs was instant. A million-node catalog still finished the walk after the kth visit already had the answer sitting on the stack.

The kth smallest key is the kth node an inorder walk visits — stop there. The BST post owns the invariant. Validate BST already showed that inorder is strictly increasing, and already wrote the iterative left-spine / pop / right walk. Here we only care about counting those pops and returning on pop k. Do not rebuild the traversal.

The problem

Given the root of a BST and an integer k, return the kth smallest value in the tree. k is 1-indexed: the leftmost key is rank 1. The prompt promises a valid BST and 1 <= k <= n. An empty tree and an out-of-range k are out of contract.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample tree and three ranks. Inorder is 1, 3, 4, 6, 7, 8, 10, 14.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      4   7

k=1  →  1     leftmost
k=3  →  4     visits 1, 3, 4
k=5  →  7     visits 1, 3, 4, 6, 7

Note: k is 1-indexed. inorder.get(k) is the off-by-one. Do not sort a list of values — a BST inorder already is the sorted order.

Dump every inorder key, then index k - 1

Walk left, visit, right. Collect every key, then return the element at k - 1. Correct. Extra list. No early exit.

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

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

At a dozen nodes this is a rounding error. At a million-node catalog you still allocate n Integers after rank k was already known. The intended walk never stores that list: decrement k on each visit and return when it hits zero.

Stop the inorder walk at visit k

Same ArrayDeque walk Validate BST used to remember the previous key. Push the left spine, pop, visit, step right. On each pop, decrement k. When k hits zero, that pop is the answer — leave the rest of the tree unvisited.

k=3
push 8, 3, 1
pop 1    k=2
pop 3    k=1    step right → 6
push 6, 4
pop 4    k=0    →  4

The Java is that walk. Deque and ArrayDeque, not java.util.Stack.

int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        k--;
        if (k == 0) {
            return current.val;
        }
        current = current.right;
    }
    return -1;
}

Time is O(h + k) — left spine to the first visit, then k pops; worst case k = n is O(n). Space is O(h) for the deque, h being height. Recursion is the same bound and a million-node spine blows the JVM stack; the loop does not. Return -1 only if the contract was broken. Under 1 <= k <= n you never need it.

Note: Recursion with a remaining-k counter is the same early exit: visit left, decrement, return this value or go right. Prefer the loop at the board unless they ask for recursion.

What interviewers usually poke next

  • BST Iterator. Same controlled inorder, one next at a time (hasNext / next). Different API; do not start yielding a stream from kthSmallest. Future path /interview/trees/medium/binary-search-tree-iterator/.
  • Left-subtree sizes. If each node stored how many keys sit in its left subtree, compare that count to k and step left/right in O(h) — no inorder walk. Pay O(h) on insert/delete to keep the counts. That is the “this tree keeps mutating” upgrade.
  • kth largest. Reverse inorder (right, visit, left), or kth smallest of n - k + 1. Name which before you flip the walk.
  • Why dump then index? It still works and pays O(n) extra memory. They gave you a BST so rank is the visit count.

You are done with this problem when you can pop 4 as rank 3 on the drawing, return without finishing the tree, and refuse to allocate an n-long list for a question that asks for one integer.