Kth Smallest Element in a BST

Problem Description

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.

Examples

Constraints

• The number of nodes in the tree is n.
• 1 ≤ k ≤ n ≤ 10⁴
• 0 ≤ Node.val ≤ 10⁴

In-Order Traversal yields Sorted Outputs

If you flatten a Binary Search Tree (BST) using in-order traversal, the values are processed in sorted ascending order. Therefore, the kth element visited during an in-order traversal is the kth smallest element.

You do not need to traverse the entire tree. An iterative in-order traversal allows you to stop and return the result the moment you visit the kth node. This prunes the remaining traversal, optimizing speed.

Solution 1: Iterative In-Order Traversal (Optimal)

Use a stack to perform the in-order traversal iteratively, decrementing k whenever a node is popped from the stack.

import java.util.Stack;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            // traverse to the leftmost node
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            k--;
            if (k == 0) return curr.val; // found the kth smallest

            curr = curr.right;
        }
        return -1;
    }
}

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        curr = root

        while curr or stack:
            # traverse to the leftmost node
            while curr:
                stack.append(curr)
                curr = curr.left

            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val  # found the kth smallest

            curr = curr.right
        return -1

#include <stack>

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        std::stack<TreeNode*> stack;
        TreeNode* curr = root;

        while (curr || !stack.empty()) {
            // traverse to the leftmost node
            while (curr) {
                stack.push(curr);
                curr = curr->left;
            }

            curr = stack.top();
            stack.pop();
            k--;
            if (k == 0) return curr->val; // found the kth smallest

            curr = curr->right;
        }
        return -1;
    }
};

Complexity Analysis:

• Time Complexity: O(h + k) where h is the tree height. We traverse down to the leftmost node O(h) and then pop k times. In the worst case (skewed tree), this is O(n); in a balanced tree, it is O(log n + k).
• Space Complexity: O(h) to store the traversal path in the stack.

Where it breaks: If the BST is modified frequently, doing a traversal per search is inefficient. If you have frequent lookup queries, you should modify the tree node structure to store the size of its left subtree, which allows O(h) lookup without traversal.

Common Mistakes

• Traversing the entire tree recursively before checking k. While running a full recursive in-order traversal and return list[k-1] works, it uses O(n) memory and time, missing the early-exit optimization.
• Off-by-one errors on index. The problem is 1-indexed, so you must decrement k and check k == 0, rather than checking indices against k - 1 without decrementing.
• Forgetting to update curr to curr.right after popping. If you omit this step, the loop will repeat and process the same nodes, resulting in an infinite loop.

Frequently Asked Questions

How do we optimize this if the BST is modified frequently? You can modify the TreeNode structure to include a size field representing the count of nodes in its subtree. The search then behaves like binary search: if left_subtree_size + 1 == k, the root is the answer. If it is larger, search left. If smaller, search right with k = k - left_subtree_size - 1. This runs in O(h) time.

Can we solve this using recursive DFS? Yes. You can use a helper class or global variables to track k and the result during recursive in-order traversal, returning early when k reaches zero.

What does this problem test in interviews? It tests your capability to write customized, early-terminating DFS loops using stacks, and your understanding of BST properties.

← All Problems