Kth Smallest in a BST

35 min · kthSmallest()

A search tree already keeps its values in order. The trick is choosing the walk that lets you cash in on that promise.

You're given the root of a valid binary search tree with distinct integer values and an integer k. Return the k-th smallest value, counting from 1.

For example, k = 1 asks for the smallest value and k = node count asks for the largest. You may trust that k always names a real node.

A few ground rules:

Every value in a node's left subtree is smaller than the node's value.
Every value in a node's right subtree is larger than the node's value.
The input tree is displayed as a level-order array, with null for a missing child.

Constraints

1 <= k <= node count <= 10_000
All node values are distinct.
-2_147_483_648 <= node.val <= 2_147_483_647

Hints

Which traversal sorts a BST?

Visit the left subtree before the node, and the right subtree after it. Write down the order produced by that walk on a three-node BST.

Count visits, not values

During an in-order traversal, the first visited node is the smallest, the second is the second smallest, and so on. Increment a counter when you visit a node.

Don't finish work you don't need

Once the counter reaches k, return that value immediately. An explicit stack makes that early stop easy to control.

Follow-up

If the tree changed often and you had to answer thousands of k queries, what extra number could each node store to make every query faster?

Visible cases

Examples

Example 1

ready

Input: root = [ 3, 1, 4, null, 2 ] k = 1
Expected: 1
Why: the first in-order visit is 1

Example 2

ready

Input: root = [ 5, 3, 6, 2, 4, null, null, 1 ] k = 3
Expected: 3
Why: in-order starts 1, 2, 3

Example 3

ready

Input: root = [ 42 ] k = 1
Expected: 42
Why: the only node is both smallest and largest

Interview signal

Asked at

AmazonGoogleUber

Full in-order list

An in-order traversal visits left subtree → node → right subtree. A BST turns that visit order into ascending values, so the direct approach collects every value and reads index k - 1.

def kth_smallest(root: TreeNode | None, k: int) -> int:
    values: list[int] = []
    stack: list[TreeNode] = []
    current = root
 
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        values.append(current.val)
        current = current.right
 
    return values[k - 1]

This works, but asking for the smallest value still walks the entire tree and stores every answer you didn't request.

Time O(n) — all nodes are visited. Space O(n) for the values and traversal stack.

Stop at the kth visit

Keep the same traversal, but count nodes as they come off the stack. At that moment the left subtree is finished, so the current node is exactly the next value in sorted order. Return as soon as the counter reaches k.

def kth_smallest(root: TreeNode | None, k: int) -> int:
    stack: list[TreeNode] = []
    current = root
    visited = 0
 
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
 
        current = stack.pop()
        visited += 1
        if visited == k:
            return current.val
        current = current.right
 
    raise ValueError("k is outside the tree")

The final error is unreachable under the input contract. It still makes the function's failure mode honest if that contract is ever broken.

Time O(h + k) — at most one root-to-leaf descent plus k visits. Space O(h) for the stack, where h is the tree's height.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayroot: TreeNode · k: int

Expected

Run: visible + custom · Submit: full suite