Kth Smallest Element in a BST
Problem statement
You are given the root of a binary search tree (BST) and a number k. Return the k-th smallest value stored in the tree, counting from 1. So k = 1 asks for the smallest value, k = 2 for the second smallest, and so on.
In a BST, every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. You can assume 1 <= k <= n, where n is the number of nodes.
The tree is written in level order: row by row, left to right, with null where a child is missing. [3,1,4,null,2] means 3 is the root, 1 and 4 are its children, 1 has no left child, and 2 is the right child of 1.
Think of a sorted index of request latencies kept as a tree: asking for the k-th smallest value is the same as asking "what is the latency at position k?"
Examples
Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: In sorted order the values are 1, 2, 3, 4. The first one is 1.

Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: In sorted order the values are 1, 2, 3, 4, 5, 6. The third one is 3.

Hints
Approach
Optimal: Iterative in-order, stop at k
Intuition
The Better approach writes every value into a list, but we only need the k-th one. So visit the nodes in the same in-order order, count them, and stop as soon as the count reaches k. No list, and no work after the answer is found.
Doing it with our own stack instead of recursion makes stopping early easy. The stack remembers the nodes we still have to come back to. To find the next smallest value: go as far left as you can, pushing each node; the top of the stack is then the smallest value not visited yet. Pop it, count it, then move to its right child and repeat.
Steps
- Start with an empty stack and
node = root. - Repeat:
- While
nodeis not empty, push it and move tonode.left. - Pop the top node. This is the next smallest value.
- Subtract 1 from
k. Ifkis now 0, return this node's value. - Set
nodeto the popped node's right child, and loop again.
- While
Dry run
root = [5,3,6,2,4,null,null,1], k = 3
| step | action | stack (bottom → top) | k left |
|---|---|---|---|
| 1 | go left from 5: push 5, 3, 2, 1 | 5, 3, 2, 1 | 3 |
| 2 | pop 1 (no right child) | 5, 3, 2 | 2 |
| 3 | pop 2 (no right child) | 5, 3 | 1 |
| 4 | pop 3 | 5 | 0 → return 3 |
Nodes 4, 5 and 6 are never visited. Edge cases: k = 1 returns the leftmost node right after the first dive; k = n visits every node and returns the rightmost one.
Complexity
Time O(H + k) - H is the height of the tree. We first walk down the left edge (H steps), then pop exactly k nodes before we stop. For a balanced tree that is O(log n + k), much less than n when k is small. In the worst case (k = n, or a line-shaped tree) it is still O(n), the same as Better.
Space O(H) - The stack only holds the nodes on the current path from the root, never more than the tree's height. That is O(log n) for a balanced tree and O(n) for a line-shaped one. There is no list of values anymore. The input tree is not counted.
from collections import deque
from typing import List, Optional
# Definition for a binary tree node (LeetCode's).
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 True:
while node is not None:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
def build_tree(values: list) -> Optional[TreeNode]:
"""Build a tree from level-order values, None = missing child."""
if not values or values[0] is None:
return None
root = TreeNode(values[0])
queue = deque([root])
i = 1
while queue and i < len(values):
node = queue.popleft()
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
if __name__ == "__main__":
print(Solution().kthSmallest(build_tree([3, 1, 4, None, 2]), 1)) # 1
print(Solution().kthSmallest(build_tree([5, 3, 6, 2, 4, None, None, 1]), 3)) # 3RecapThe whole problem in a few lines, for the night before
- Spot it: kth smallest value in a binary search tree
- Idea: inorder traversal of a BST visits values in sorted order; count while visiting and stop at the kth
- Cost: O(h + k) time, O(h) space (h is the tree height)
- Trap: k is 1-based, and stop early instead of traversing the whole tree
Interview follow-ups
The BST is changed often (inserts and deletes) and you need the k-th smallest many times. How would you speed it up?
Store in every node the size of its subtree (how many nodes are below it, including itself), and update these counts on each insert and delete. To find the k-th smallest, look at the left subtree's size
L. Ifk <= L, go left; ifk == L + 1, the current node is the answer; otherwise go right withk - L - 1. Each query then costs O(H) instead of O(H + k), which is O(log n) on a balanced tree.What if
kcan be larger than the number of nodes?The code as written assumes
k <= n. Handle it by checking the stack: if you need to pop but the stack is empty andnodeis empty, the tree ran out of values, so return a signal such as-1(this is what the GeeksforGeeks version asks for). The cost does not change.The tree is huge and very deep. Is recursion safe?
A line-shaped tree with 100,000 nodes can exceed the default recursion limit in Python and overflow the call stack in Java or C++. The iterative optimal approach avoids this because its stack lives on the heap. That is another reason to prefer it in production code.
Frequently asked questions
In-order visits the left subtree, then the node, then the right subtree. In a BST everything on the left is smaller than the node and everything on the right is larger. So each node is printed after all smaller values and before all larger ones. Apply that at every node and the whole output is sorted.
Yes. You can keep a counter in a recursive in-order walk and stop when it reaches k; it has the same O(H + k) time and O(H) space. The iterative version is shown because stopping early is simpler: you just return. With recursion you need a flag or a shared variable so the outer calls stop too.
There is a technique called Morris traversal that walks a tree in order without a stack by temporarily rewiring pointers. It works, but it is tricky to get right in an interview and it changes the tree while it runs. For infra coding rounds the stack-based version is what interviewers expect.
Do a reverse in-order walk: right subtree, then node, then left subtree. That visits values from largest to smallest, so the k-th node you visit is the k-th largest. Everything else in the optimal approach stays the same.
Ordered data shows up everywhere in infra: sorted indexes, time-ordered event stores, and percentile lookups on latency data. "Give me the value at position k" on ordered data is exactly a percentile query. The problem also checks that you can traverse a tree without building a full copy of it, which matters when the data is large.
