Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1 Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Approach: Iterative In-order Traversal (Optimal Solution)

Algorithm

1. Use an explicit stack to simulate in-order traversal
2. Repeatedly push the left children onto the stack
3. When there is no left child, pop a node, decrement k, and check if it has become 0
4. If k == 0, the popped node is the answer
5. Otherwise move to the node’s right subtree and continue

Key Insight

In-order traversal of a BST visits nodes in ascending order. The kth node visited is exactly the kth smallest. The iterative version stops as soon as the answer is found, avoiding traversal of the whole tree.

Time & Space Complexity

• Time Complexity: O(n) in the worst case - the traversal stops after visiting k nodes, and k <= n
• Space Complexity: O(n) - the stack holds at most the tree height

Java Implementation

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class KthSmallestElementInABst {

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

Example Walkthrough

For root = [5,3,6,2,4,null,null,1], k = 3:

1. Push 5, 3, 2, 1 → pop 1 (k=2), move right (null)
2. Pop 2 (k=1), move right (null)
3. Pop 3 (k=0) → return 3

Alternative Approach: Recursive In-order Traversal

public class KthSmallestRecursive {

    private int count;
    private int result;

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

    private void inorder(TreeNode root) {
        if (root == null || count == 0) {
            return;
        }
        inorder(root.left);
        if (--count == 0) {
            result = root.val;
            return;
        }
        inorder(root.right);
    }
}

The recursive variant has the same logic but uses the call stack instead of an explicit stack.

Follow-up Optimization: Subtree Size Counts

For a frequently-modified BST with many kth-smallest queries, augment each node with the size of its subtree. The search then descends in O(h) time:

• Let leftSize be the number of nodes in the left subtree
• If k == leftSize + 1, the current node is the answer
• If k <= leftSize, search the left subtree; otherwise search the right subtree with k -= leftSize + 1

This turns each query from O(n) into O(h) and supports O(h) insert/delete when the subtree counts are updated along the way.

Key Insights

1. In-order Ordering: BST in-order traversal produces sorted output, so the kth visited node is the kth smallest
2. Early Termination: The loop stops the moment k reaches zero, visiting only k nodes
3. Iterative vs Recursive: The iterative version avoids recursion depth concerns on skewed trees
4. Node Counts: Precomputing subtree sizes answers repeated queries in O(h) instead of O(n)

The iterative in-order traversal is the optimal solution, providing O(k) time and O(h) space.