Kth Smallest Element in a BST

Solving tips

Key insight: an in-order traversal of a BST yields values in sorted order, so the k-th node visited in-order is the answer — no sorting needed.
Don't store the whole list; keep a countdown and stop the instant it hits zero for O(h + k) time, O(h) space.
An explicit-stack iterative in-order (push left spine, pop, decrement k, go right) makes the early exit a clean return and avoids recursion-depth issues.
Pitfall: decrement/count exactly when a node is visited in-order (after the left recursion, before going right); and don't assume O(log n) height — a skewed BST has h = n.

Problem

You are given the root of a binary search tree and an integer k. Return the k-th smallest value stored in the tree, counting from 1 (so k = 1 means the minimum). The BST property holds everywhere: every node’s left subtree contains only smaller values and its right subtree only larger values, and all values are distinct.

Examples

Input: root = [3,1,4,null,2], k = 1 → Output: 1 The sorted order of values is [1, 2, 3, 4]; the 1st smallest is 1.
Input: root = [5,3,6,2,4,null,null,1], k = 3 → Output: 3 Sorted order is [1, 2, 3, 4, 5, 6]; the 3rd smallest is 3.
Input: root = [2,1,3], k = 3 → Output: 3 Sorted order is [1, 2, 3]; the 3rd smallest is the maximum, 3.

Constraints

The tree has n nodes with 1 <= k <= n <= 10^4.
0 <= Node.val <= 10^4.
An O(n) pass is fine; the interesting goal is stopping early after k nodes instead of always visiting all n.

Think about it first

Hint 1

What traversal order visits a BST's values in sorted order?

Hint 2

If an inorder traversal yields values smallest-first, you don't need the whole sorted list — you only need to count how many nodes you've visited so far.

Hint 3

Do an iterative inorder traversal with an explicit stack: push left spine, pop a node, decrement `k`; when `k` hits 0, the just-popped node is the answer.

TL;DR

Inorder traversal, stop after k nodes — O(h + k) time, O(h) space (h = tree height).

Approach 1 — Brute force: collect everything, then sort/index

The naive move ignores the BST property entirely: gather every value with any traversal, sort the list, and take index k - 1.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

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

        collect(root)
        vals.sort()
        return vals[k - 1]

Complexity: O(n log n) time, O(n) space. With n <= 10^4 this actually passes, but the sort is pure waste — the tree already is sorted data, so throwing that structure away and re-sorting is the tell that we’ve missed the point.

Approach 2 — Recursive inorder with an early-stopping counter

The insight: an inorder traversal (left, node, right) of a BST visits values in strictly increasing order. So the k-th node visited inorder is the answer — no list, no sort. Keep a countdown and abort the recursion the moment it reaches zero.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.remaining = k
        self.answer = -1

        def inorder(node: Optional[TreeNode]) -> None:
            if not node or self.remaining == 0:
                return
            inorder(node.left)
            if self.remaining == 0:
                return
            self.remaining -= 1
            if self.remaining == 0:
                self.answer = node.val
                return
            inorder(node.right)

        inorder(root)
        return self.answer

Walkthrough on root = [5,3,6,2,4,null,null,1], k = 3: inorder dives left to 1 (remaining 3→2), backs up to 2 (2→1), backs up to 3 (1→0) — answer recorded as 3; every check of remaining == 0 from here on returns immediately, so 4, 5, 6 are never processed.

Complexity: O(h + k) time (walk down the left spine, then visit k nodes), O(h) recursion stack.

Approach 3 — Iterative inorder with an explicit stack (the classic)

The insight: the same traversal can be driven by an explicit stack — push the left spine, pop, step right — which makes the early exit a plain return instead of threaded flags, and avoids recursion-depth worries on skewed trees.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

Walkthrough on root = [3,1,4,null,2], k = 1: push 3, push 1 (no left child) → pop 1, k becomes 0 → return 1. Two pushes, one pop — the nodes 2, 3, 4 are never touched.

Complexity: O(h + k) time, O(h) stack space.

Follow-up worth knowing: if the tree is modified often and kthSmallest is called repeatedly, augment each node with the size of its left subtree; then each query walks one root-to-node path in O(h) by comparing k against subtree sizes (an order-statistics tree).

Common pitfalls

Decrementing k at the wrong spot (before recursing left, or after moving right) — the count must happen exactly when a node is visited inorder.
Forgetting the early exit in the recursive version, so the traversal keeps mutating state after the answer is found and can overwrite it.
Off-by-one: k is 1-indexed, so the brute force needs vals[k - 1].
Assuming O(log n) height — a skewed BST has h = n, so “O(k)” claims that ignore the left-spine descent are wrong.

Pattern takeaway

Inorder traversal of a BST is a sorted stream. Any “k-th / rank / range” question on a BST is really a question about consuming that stream lazily — iterate with an explicit stack, count as you pop, and stop the moment you have what you need.