Kth Smallest Element in BST: inorder traversal, stop at kth

• BST property – inorder traversal (left, node, right) visits values in strictly ascending order.
• Kth smallest – the kth node visited in inorder is the kth smallest element.
• Iterative inorder – use an explicit stack for clean early stopping: push left, pop and process, go right.
• Early stop – decrement k on each pop; when k reaches zero, the current node is the answer.
• Complexity – O(H + k) time, O(H) space, where H is the tree height.

What is the problem?

Given the root of a binary search tree and an integer k, return the kth smallest value. For example, in a BST containing [1, 2, 3, 4, 5], the 3rd smallest is 3.

At the National Bank of India, account balances are indexed in a BST for fast lookup. The analytics team needs the kth smallest balance for low-balance reviews.

Why does inorder traversal give sorted order?

In a BST, every node's left subtree contains smaller values and the right subtree contains larger values. Inorder traversal visits left, then node, then right, which naturally produces ascending order.

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Inorder: 1, 2, 3, 4, 5, 6, 7 (sorted)

How does the iterative inorder with early stopping work?

package com.bank.analytics;

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

public class KthSmallestBST {
    public static int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            k--;
            if (k == 0) return curr.val;
            curr = curr.right;
        }
        throw new IllegalArgumentException("k is larger than tree size");
    }

    public static void main(String[] args) {
        // BST:     4
        //         / \
        //        2   6
        //       / \
        //      1   3
        TreeNode root = new TreeNode(4,
            new TreeNode(2, new TreeNode(1), new TreeNode(3)),
            new TreeNode(6));
        System.out.println("3rd smallest: " + kthSmallest(root, 3));
    }
}

3rd smallest: 3

Why prefer iterative over recursive for early stopping?

The iterative approach with an explicit stack naturally stops when k reaches zero. The recursive approach would need to carry a counter through the recursion and either use a class field or throw an exception to break out early.

// Recursive: awkward early stopping
int count = 0;
int result = -1;
void inorder(TreeNode node, int k) {
    if (node == null || count >= k) return;
    inorder(node.left, k);
    count++;
    if (count == k) { result = node.val; return; }
    inorder(node.right, k);
}

// Iterative: clean early stopping
if (k == 0) return curr.val; // immediate return

What is the time and space complexity?

| Aspect | Complexity |
|---|---|
| Time | O(H + k), descend to smallest then visit k nodes |
| Space | O(H) for the stack |
| Balanced tree H | O(log n) |
| Skewed tree H | O(n) |

When k is small, this is far cheaper than traversing all n nodes.

What is the follow-up: augmented BST with subtree sizes?

If the tree changes frequently and kth-smallest queries are common, augment each node with the size of its left subtree. Then navigate directly:

public static int kthSmallestAugmented(AugTreeNode node, int k) {
    while (node != null) {
        int leftSize = (node.left != null) ? node.left.size : 0;
        if (k == leftSize + 1) {
            return node.val;
        } else if (k <= leftSize) {
            node = node.left;
        } else {
            k = k - leftSize - 1;
            node = node.right;
        }
    }
    throw new IllegalArgumentException("k out of range");
}

Each query is O(H) with no traversal beyond the path from root to the answer.

What are common mistakes?

Decrementing k before popping, which counts nodes that have not been visited yet.

// Wrong: decrement before pop
k--;
curr = stack.pop();
// k is off by one

// Correct: pop first, then decrement
curr = stack.pop();
k--;
if (k == 0) return curr.val;

What are the edge cases?

• k = 1: return the leftmost (smallest) node.
• k = n: return the rightmost (largest) node.
• k > n: invalid; throw an exception.
• Single node tree: if k = 1, return the root value.

What should a senior engineer know?

The augmented BST trades O(n) extra space (one integer per node) and O(log n) bookkeeping per insert/delete for O(H) query time without any traversal. This is the standard answer for the "frequent kth-smallest queries" follow-up.

For self-balancing trees (AVL, Red-Black), H is O(log n), making both the traversal and augmented approaches efficient.

What are common interview follow-up questions?

• What if the tree is modified frequently? (Augment with subtree sizes.)
• Kth largest instead of smallest? (Reverse inorder: right, node, left.)
• What if k changes between queries? (Augmented BST handles any k in O(H).)