Kth Smallest Element in a BST

MediumTree DFSBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given the root of a binary search tree and an integer k. In a binary search tree, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger. Return the k-th smallest value among all the nodes, where k is 1-indexed (k = 1 means the minimum). k is always between 1 and the number of nodes.

Examples

root = [3,1,4,null,2], k = 1 returns 1

1 is the smallest value in the tree.

In sorted order the values are 1, 2, 3, 4, so the 1st smallest is 1.

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

The 3rd smallest value, 3, has 1 and 2 below it.

In sorted order the values are 1, 2, 3, 4, 5, 6, so the 3rd smallest is 3. It is not a leaf: the two smaller values, 2 and 1, sit below it on the left.

Constraints

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

Hints

Hint 1

In a binary search tree, is there a visiting order that produces the values already sorted?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

An in-order depth-first traversal (left, node, right) of a binary search tree visits values in ascending order, so the k-th node visited is the answer. Do it iteratively with an explicit stack: push nodes down the leftmost path, pop one (the next smallest), count it, then move to its right child and repeat. Stopping at the k-th pop means only O(h + k) nodes are touched. O(h + k) time, O(h) space, h = tree height.

Time

O(h + k)

Space

O(h)

Pitfall

In a recursive version, a counter passed as a plain int parameter is copied into each call, so the visits counted in a left subtree are lost. Keep the count in a field (or use an explicit stack) and stop as soon as it reaches k.

Solutions

class Solution {
    public 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();
            if (--k == 0) return curr.val;
            curr = curr.right;
        }
        return -1;
    }
}

from typing import Optional

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