The k-th smallest value in a search tree

Trees Mid-level Python 3.13+ Reviewed By Best Latest Apps

Order the steps

Put the explicit-stack in-order walk in order.

  • Push the current node and move to its left child until you reach None
  • Count it; if this is the k-th node, return its value
  • Pop the top node from the stack
  • Move to the popped node's right child and repeat

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A C B D

  1. Push the current node and move to its left child until you reach None The smallest value left is at the bottom of the leftmost path.
  2. Pop the top node from the stack It is the next value in sorted order.
  3. Count it; if this is the k-th node, return its value Stopping here avoids walking the rest of the tree.
  4. Move to the popped node's right child and repeat Values just above the popped one live in its right subtree.
The search tree 8, 3, 10, 1, 6, 14, 4, 7 visited in order: the values come out sorted, and the third one is 4.

Steps come from running the Python solution.

Text version

inorder:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 1
  2. Visit 3
  3. Visit 4
  4. Visit 6
  5. Visit 7
  6. Visit 8
  7. Visit 10
  8. Visit 14

Result: 4. Order: 1, 3, 4, 6, 7, 8, 10, 14

preorder:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 8
  2. Visit 3
  3. Visit 1
  4. Visit 6
  5. Visit 4
  6. Visit 7
  7. Visit 10
  8. Visit 14

Result: [8, 3, 1, 6, 4, 7, 10, 14]. Order: 8, 3, 1, 6, 4, 7, 10, 14

30-second answer

An in-order walk of a search tree visits values in increasing order. Walk in order with an explicit stack and stop at the k-th value. O(h + k) time and O(h) space, which is much less than sorting all n values when k is small.

Practise saying it · 45 s. No recording, just a timer

Explain the k-th smallest in a search tree.

Say your answer out loud, then check which of these points you covered:

  • In-order is sorted
  • Explicit stack
  • O(h + k)

Deep dive

The explicit-stack in-order walk is worth knowing by heart; it also powers search-tree iterators.

If the tree changes often and k-th queries are frequent, store subtree sizes in each node for O(h) queries.

Collecting the whole in-order list is O(n) and fine as a first answer.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def kth_smallest(root: Node | None, k: int) -> int:
    stack: list[Node] = []
    node, seen = root, 0
    while True:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        seen += 1
        if seen == k:
            return node.val
        node = node.right

Common mistakes

  • Doing a pre-order or level-order walk, which is not sorted.
  • Off-by-one: k is usually 1-based.

Senior take & follow-ups

Say 'in order is sorted' first; everything follows from it.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you support inserts and k-th queries together?

    Show hint

    Keep a size field per node and update it on insert.

  2. How do you find the k-th largest?

    Show hint

    Walk in reverse order: right, node, left.

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.