Command Palette

Search for a command to run...

Hectal
Problem 17.4 · Binary Search TreesMedium

Kth Smallest Element in a BST

PatternBST Ordering

What it teaches: In-order is sorted, so count as you walk and stop at k.

Practise it on judges as “Kth Smallest Element in a BST”.

The problem

Return the k-th smallest value (1-indexed) in a BST.

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

  • 1 ≤ k ≤ n ≤ 10⁴

Pattern clues in the wording

  • → Rank question on a BST

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

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

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Iterative in-order with early stop · O(h + k)
1

Iterative in-order with early stop

Time O(h + k) Space O(h)

Push left spine, pop, count; when the count reaches k, return the value.

▶ Dry run: k = 3root = [5, 3, 6, 2, 4, null, null, 1], k = 3
1↑cur23456

stack(stack)

5321

Step 1/3Push the left spine: 5, 3, 2, 1.

Approach 1
import java.util.ArrayDeque;
import java.util.Deque;

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

Verdict: Stops early.

Before you submit

Edge cases and common mistakes

Test these inputs

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

Mistakes people make

  • Collecting the whole in-order list when only k values are needed.

Interview

Follow-up questions

What if the tree changes often and you ask many k-th queries?