Kth Smallest Element in a BST — Iterative Inorder Early Exit

This is a one-line problem hiding a two-paragraph follow-up. The one-liner: inorder traversal of a BST visits values in sorted order, so the kth visited node is the answer. The follow-up — “What if the tree is modified often and you need many kth queries?” — is where interviewers separate the rehearsed from the prepared.

The Problem

Given the root of a BST and an integer k, return the kth smallest value in the tree. Assume 1 <= k <= n, where n is the number of nodes.

Intuition

Inorder traversal on a BST yields sorted order. So instead of flattening the entire tree and indexing into the result, run an iterative inorder traversal and stop the instant you have popped k nodes. For small k, this finishes in O(h + k) instead of O(n).

Explanation with Example

Use the BST [5, 3, 6, 2, 4, null, null, 1] with k = 3.

• Push 5, then 3, then 2, then 1. Stack: [5, 3, 2, 1]. Node is null.
• Pop 1. k becomes 2. Move right — null.
• Pop 2. k becomes 1. Move right — null.
• Pop 3. k becomes 0. Return 3.

We never touched 4, 5, or 6. The early exit pays off.

BST:                inorder visit order:
      5            1, 2, 3, 4, 5, 6
     / \
    3   6          stack walk (k=3):
   / \             push 5 -> push 3 -> push 2 -> push 1
  2   4            pop 1  k=2
 /                 pop 2  k=1
1                  pop 3  k=0 -> return 3
                   (4, 5, 6 never visited)

Code

def kthSmallest(root, k):
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

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

int kthSmallest(TreeNode* root, int k) {
    std::stack<TreeNode*> st;
    TreeNode* node = root;
    while (!st.empty() || node) {
        while (node) {
            st.push(node);
            node = node->left;
        }
        node = st.top(); st.pop();
        if (--k == 0) return node->val;
        node = node->right;
    }
    return -1;
}

Edge Cases

• A skewed tree that is purely left children — the inner while walks all the way down before any pop, so the first iteration is O(h).
• k equals the total number of nodes — we end up traversing the entire tree.
• A tree with a single node and k = 1 — handled by the loop body.
• Duplicates — the standard BST definition forbids them, so the problem is well-defined.

Complexity Analysis

Time is O(h + k), where h is the height. For balanced trees this is O(log n + k), for skewed it is O(n). Space is O(h) for the explicit stack. The brute force is O(n) time and O(n) space regardless of k.

If you reach for recursion, the cost is the same but the call stack is implicit.

How to Explain It in an Interview

Start with the invariant: inorder on a BST yields sorted order. Then make the optimization explicit: you do not have to finish the traversal — pop until k hits zero. Walk through the iterative inorder loop once because it is the kind of code people forget under pressure.

Then volunteer the follow-up before it is asked: “If the BST is modified often and we need many kth queries, augment each node with a count of nodes in its subtree. Then locating the kth smallest becomes a guided walk in O(h).” This single sentence reliably moves the conversation forward.

Related Problems

• Validate Binary Search Tree
• Binary Search Tree Iterator (same iterative-inorder skeleton)
• Convert BST to Greater Tree (reverse inorder)
• Closest BST Value

Many of these reuse the same stack pattern. For more on traversal order intuition, revisit Binary Tree Traversals.

Wrap up

This problem is a chance to show three things in one answer: that you know inorder yields sorted order, that you can write iterative tree code cleanly, and that you have thought past the literal prompt to the maintenance-heavy follow-up. The augmented-tree mention is what separates a passing answer from a strong-hire one.

If recursion still feels shaky, the recursion fundamentals post is the right warm-up before drilling this problem.