Kth Smallest Element in a BST

Medium Problem 74 of 151 Java and Python

Problem

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) among all node values.

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⁴

Explanation

Inorder traversal visits a BST's values in sorted order, so the k-th value visited is the answer.

Use the iterative traversal so you can stop the moment you reach it, instead of listing the whole tree.

Approach 1 · Naive

Full inorder list

Time O(n)
Space O(n)

List every value in inorder and return index k - 1.

Collect all values with an inorder traversal.
Return values[k - 1].

Java

import java.util.*;

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

    private void inorder(TreeNode node, List<Integer> values) {
        if (node != null) {
            inorder(node.left, values);
            values.add(node.val);
            inorder(node.right, values);
        }
    }
}

Python

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

        def inorder(node):
            if node:
                inorder(node.left)
                values.append(node.val)
                inorder(node.right)

        inorder(root)
        return values[k - 1]

Approach 2 · Optimal

Iterative inorder, stop at k

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

Walk the tree in order with an explicit stack and count nodes as you pop them.

Push nodes while going left.
Pop a node and decrement k; if k == 0, return its value.
Move to its right child and repeat.

Java

import java.util.*;

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

Python

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

Complexity compared

Approach	Time	Space
Naive Full inorder list	O(n)	O(n)
Optimal Iterative inorder, stop at k	O(h + k)	O(h)

Key takeaways

Follow-up (frequent inserts and queries): store the size of each subtree in its node to find the k-th in O(h).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem