Kth Smallest Element in a BST

mediumTrees: BST & Advanced34 stepsJava · Python · C++

An in-order traversal of a BST visits values in sorted order. Walk it iteratively with a stack: go left as far as possible, pop, count, then move right. The k-th popped node is the answer.

▶ Watch the animated trace

Traced input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3 → 3. Original problem: neetcode.io/problems/kth-smallest-integer-in-bst

Complexity

BestO(h + k)

AverageO(h + k)

WorstO(n)

SpaceO(h)

You can stop after k pops instead of traversing the whole tree.

Key idea

In-order (left, node, right) on a BST is sorted ascending.
An explicit stack lets you stop early once k nodes are counted.
Push the whole left spine before popping.

Common mistakes

Collecting all values into a list first is O(n) time and space.
Off-by-one: k is 1-indexed.

Solution

Java

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

Python

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack, curr, count = [], root, 0
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        count += 1
        if count == k:
            return curr.val
        curr = curr.right
    return -1

C++

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

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
k = 1 The leftmost node.	`root = [3, 1, 4, null, 2], k = 1`	`1`
k = n The rightmost node.	`root = [2, 1, 3], k = 3`	`3`
Right-skewed No left spine at all.	`root = [1, null, 2, null, 3], k = 2`	`2`