Kth Smallest Element in a BST Solution

Problem

Given the root of a binary search tree and an integer k, find the kth smallest value among all nodes (k is 1-indexed). Every node value is unique.

[3,1,4,null,2]

Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: The sorted order of values is [1, 2, 3, 4], so the 1st smallest is 1.

[5,3,6,2,4,null,null,1]

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: Sorted order is [1, 2, 3, 4, 5, 6], so the 3rd smallest is 3.

Intuition

In-order traversal of a BST (left → node → right) visits nodes in ascending sorted order — that's the defining property of a BST. So the answer is simply the kth node we visit during an in-order traversal. The brute-force collects all values first; the optimal version stops the moment we've counted k nodes.

Approach 1 — Recursive In-Order (Collect All)

Recursively traverse the tree in order, appending every value to a list. Once the traversal finishes, return the element at index k − 1.

Recursively visit the left subtree.
Append the current node's value to the results list.
Recursively visit the right subtree.
After the full traversal, return results[k - 1].

1from typing import Optional, List
2
3def kthSmallest(root: Optional['TreeNode'], k: int) -> int:
4    collected = []
5
6    def inorder(node):
7        if not node:
8            return
9        inorder(node.left)
10        collected.append(node.val)   # visit order is sorted in a BST
11        inorder(node.right)
12
13    inorder(root)
14    return collected[k - 1]          # k is 1-indexed

Time: O(n) — visits every node to build the full sorted list.

Space: O(n) — stores all n values, plus O(H) recursion stack.

Approach 2 — Iterative In-Order with Early Stop

Simulate in-order traversal using an explicit stack. The moment we've popped the kth node, we return its value — we never process the rest of the tree.

Start with current = root and an empty stack.
Push current and all its left descendants onto the stack (descend as far left as possible).
Pop the top node and decrement the counter.
If the counter reaches zero, return this node's value.
Otherwise, move to the right subtree and repeat from step 2.

1from typing import Optional
2
3def kthSmallest(root: Optional['TreeNode'], k: int) -> int:
4    stack = []
5    current = root
6    remaining = k
7
8    while current or stack:
9        while current:                  # descend to the leftmost node
10            stack.append(current)
11            current = current.left
12
13        current = stack.pop()           # this is the next in-order node
14        remaining -= 1
15        if remaining == 0:
16            return current.val          # found the kth smallest — stop early
17
18        current = current.right         # explore right subtree next
19    
20    return -1  # unreachable given valid constraints

Time: O(H + k) — O(H) to reach the leftmost node, then k steps to count up. For a balanced BST, H = O(log n).

Space: O(H) — the stack holds at most one path from root to a leaf.

Complexity Summary

Approach	Time	Space	When to use
Recursive In-Order	O(n)	O(n)	When you need all values sorted anyway, or k is unknown until runtime
Iterative Early Stop	O(H + k)	O(H)	Interview setting or large trees where k is small relative to n

Common Mistakes

Using pre-order or post-order traversal instead of in-order — only in-order produces sorted values in a BST; the other orderings give no useful ordering guarantee.
Off-by-one on the return index — k is 1-indexed, so Approach 1 returns collected[k - 1], not collected[k].
Forgetting to move to the right subtree — in Approach 2, after popping a node, you must set current = current.right. Omitting this skips entire right subtrees and produces wrong answers.
Assuming a balanced tree — the stack in Approach 2 can hold O(n) nodes if the tree is skewed (all left children), not O(log n). Bounds depend on actual tree height H.
Checking the counter before decrementing — decrement first, then check for zero; checking before decrement would return the (k−1)th smallest instead.

Kth Smallest Element in a BST — Solution