Start practising

Kth Smallest Element in a BST

Medium Trees & BST Reverse Inorder Traversal Original on LeetCode

Kth Smallest Element in a BST is a medium trees & bst problem solved with the reverse inorder traversal pattern. The best approach, optimal (iterative inorder, stop early), runs in O(h + k) time and O(h) space. Below are 2 approaches in Java, from inorder into a list up.

Problem

Given the root of a BST and an integer k, return the k-th smallest value (1-indexed).

Examples

Example 1

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

Example 2

Input
root = [2, 1, 3], k = 1
Output
1

Constraints

  • 1 <= k <= n <= 10^4

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Inorder into a listO(n)O(n)
Optimal (iterative inorder, stop early)O(h + k)O(h)

1Inorder into a list

TimeO(n)
SpaceO(n)

Collect the full inorder traversal and return element k - 1.

  1. inorder(root, list); return list.get(k - 1).
Java
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        return vals.get(k - 1);
    }

    private void inorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out);
        out.add(n.val);
        inorder(n.right, out);
    }
}

2Optimal (iterative inorder, stop early)

TimeO(h + k)
SpaceO(h)

Run the stack-based inorder and count visited nodes. The k-th visit is the answer, so you never touch the rest of the tree.

  1. Push the left spine; pop; if --k == 0 return val; go right.
Java
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;
        while (true) {
            while (cur != null) { st.push(cur); cur = cur.left; }
            cur = st.pop();
            if (--k == 0) return cur.val;
            cur = cur.right;
        }
    }
}

Edge cases to test

  • k = 1 (the minimum) or k = n (the maximum)

Hints

Hint 1

Inorder traversal of a BST visits values in increasing order. Stop at the k-th one.

FAQ

What is the best time complexity for Kth Smallest Element in a BST?

Optimal (iterative inorder, stop early) runs in O(h + k) time and O(h) extra space.

Which pattern does Kth Smallest Element in a BST use?

It is a trees & bst problem that uses the reverse inorder traversal pattern. Other problems with the same pattern: Kth Largest Element in BST.

Is there a brute force solution for Kth Smallest Element in a BST?

Yes. Inorder into a list takes O(n) time and O(n) space. Collect the full inorder traversal and return element k - 1.

Which edge cases should I test for Kth Smallest Element in a BST?

k = 1 (the minimum) or k = n (the maximum).