Kth Smallest Element in a BST

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

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

This approach ignores the BST property: 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

def kthSmallest(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 passes, but the sort is redundant work: the tree already holds its values in sorted order, so flattening and re-sorting discards that structure.

Approach 2 — Recursive inorder with an early-stopping counter

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. There is no need to build a list or sort. Keep a countdown and stop the recursion once it reaches zero.

For the second example, root = [5,3,6,2,4,null,null,1], the tree looks like:

graph TD
  N5["5"] --> N3["3"]
  N5 --> N6["6"]
  N3 --> N2["2"]
  N3 --> N4["4"]
  N2 --> N1["1"]

Inorder traversal yields 1, 2, 3, 4, 5, 6, so with k = 3 the answer is 3.

# 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

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

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

    inorder(root)
    return 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), and records the answer as 3. Every later check of remaining == 0 returns immediately, so 4, 5, and 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 same traversal can be driven by an explicit stack: push the left spine, pop, step right. This makes the early exit a plain return instead of threaded flags, and avoids recursion-depth limits 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

def kthSmallest(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 and one pop; the nodes 2, 3, and 4 are never touched.

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

Follow-up: if the tree is modified often and kthSmallest is called repeatedly, augment each node with the size of its left subtree. Each query then 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 produces a sorted stream. Any “k-th / rank / range” question on a BST is a question about consuming that stream lazily: iterate with an explicit stack, count as you pop, and stop once you have what you need.