Kth Smallest Element In a Bst

MEDIUM✓ CHIP-TIMEDLC #230 — FULL STATEMENT ↗

The drill: Find the k-th smallest value stored in a BST — the tree's shape encodes sorted order for free, if you traverse it the right way.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary search tree and a rank k arrive together, and the task is naming which value sits at position k when every node's value is listed in ascending order.

BSTs already encode sorted order in their shape — the way you walk it decides whether you're rediscovering that order the hard way or reading it off for free.

k always falls inside the number of nodes present, so the only real question is finding the value that lands at that rank and returning it.

EX 01

root = [3, 1, 4] · k = 1

→ 1

SMALLEST

EX 02

root = [3, 1, 4] · k = 2

→ 3

MIDDLE

EX 03

root = [3, 1, 4] · k = 3

→ 4

LARGEST

k always falls within the tree's actual node count
tree sizes reach into the tens of thousands
values are unique across the tree, consistent with BST ordering
k is 1-indexed — k=1 means the smallest value

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A BST's inorder traversal visits values in ascending sorted order — that fact alone solves most of this problem.

HINT 2 THE STRUCTURE

You don't need every value, just the k-th one. What lets a traversal stop the instant it produces the k-th value, instead of finishing the whole tree?

HINT 3 ONE STEP FROM THE ANSWER

Iterative inorder with an explicit stack: push left spines, pop, count each pop — the k-th pop's value is the answer, and the stack lets you return immediately.

COACH'S BOARD — THE PATTERN, STEP BY STEP

STOP AT THE K-TH POPPATTERN · STOP AT THE K-TH POProot = [5, 3, 8, 1, 4, 7, 9] · k = 4

STACK

— empty —

STEP 1

Push every left child down to the bottom — the stack's TOP is always the next-smallest unvisited value. Target k=4.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/kth-smallest-element-in-a-bst.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(H + K)SPACE O(H)PYTHON · RACE PACE · 15 LN

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

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)

        inorder(root)
        return result[k - 1]

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 13 LN

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

TIME O(H + K)SPACE O(H)JAVA · RACE PACE · 20 LN

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

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

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED