Skip to main content
DSA patterns

Kth Smallest Element in a BST

mediumTreesAmazonGoogleUber

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 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.

Example 2

Hints

Hint 1: Collecting every value and sorting works. But a BST is already ordered — can you read the values out in sorted order without sorting?

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

  1. Start with an empty stack and node = root.
  2. Repeat:
    • While node is not empty, push it and move to node.left.
    • Pop the top node. This is the next smallest value.
    • Subtract 1 from k. If k is now 0, return this node's value.
    • Set node to the popped node's right child, and loop again.

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))  # 3
RecapThe 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. If k <= L, go left; if k == L + 1, the current node is the answer; otherwise go right with k - L - 1. Each query then costs O(H) instead of O(H + k), which is O(log n) on a balanced tree.

  • What if k can 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 and node is 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.