Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

The problem in plain language

Given the root of a binary search tree and a 1-indexed number k, return the value that would appear in position k if all node values were arranged from smallest to largest.

One solution is to collect every value, sort the list, and index into it. That works for any binary tree, but it ignores the most useful part of the input: a binary search tree already stores its values in an ordered structure. The goal is to read that order directly and stop as soon as the answer appears.

Deriving the optimal approach

For every node in a binary search tree, all values in its left subtree are smaller and all values in its right subtree are larger. An inorder traversal follows exactly that arrangement: visit the left subtree, then the node, then the right subtree. The values therefore arrive in increasing order.

Imagine placing a counter beside that traversal. The first visited node is the smallest, the second is the second-smallest, and so on. The moment the counter reaches k, the current node is the answer; no sorting and no traversal of the remaining larger values are needed.

Recursion expresses inorder traversal neatly, but an explicit stack makes the control flow and the early stop especially clear. Repeatedly push the current node and move left until there is nowhere else to go. Pop the nearest unfinished node, count it, and then begin the same process in its right subtree.

This returns the correct value because the stack reproduces inorder traversal exactly. Before a node is popped, every smaller node in its left subtree has been visited. Its right subtree is postponed until after the node, so no larger value can be counted too early.

If the tree height is h, reaching the first value takes at most h downward steps and finding the answer visits at most k nodes. The time complexity is O(h + k), which is O(n) in the worst case. The stack holds at most one root-to-leaf path, so the extra-space complexity is O(h). In a balanced tree, h is O(log n); in a completely skewed tree, it can be O(n).

Python solution

from __future__ import annotations

from collections.abc import Iterator
from typing import Optional


class TreeNode:
    """A node in a binary tree."""

    def __init__(
        self,
        val: int = 0,
        left: Optional[TreeNode] = None,
        right: Optional[TreeNode] = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        """Return the k-th smallest BST value, with k counted from one."""
        if k < 1:
            raise ValueError("k must be at least 1")

        for position, value in enumerate(self._inorder_values(root), start=1):
            if position == k:
                return value

        # LeetCode guarantees that k is valid. Keeping this check makes the
        # method fail clearly if it is reused with an empty or too-small tree.
        raise ValueError("k exceeds the number of nodes in the tree")

    @staticmethod
    def _inorder_values(root: Optional[TreeNode]) -> Iterator[int]:
        """Yield tree values in the order produced by iterative inorder DFS."""
        stack: list[TreeNode] = []
        current = root

        while current is not None or stack:
            # Save the path so each node can be processed after its left side.
            while current is not None:
                stack.append(current)
                current = current.left

            current = stack.pop()
            yield current.val
            current = current.right

Interview follow-ups

Can you write the traversal recursively?

Use a recursive inorder depth-first search and keep a remaining-rank counter outside the helper. After returning from the left subtree, decrement the counter for the current node; when it becomes zero, save the node’s value and stop exploring.

This works for the same reason as the iterative solution: recursive call order is still left, node, right. Its time and auxiliary-space bounds are also O(h + k) and O(h). The tradeoff is that the call stack is controlled by Python. A highly skewed tree can exceed the recursion limit, while an explicit stack handles that shape safely.

What if the same tree receives many rank queries?

Augment each node with the size of its subtree. At a node whose left subtree contains left_size nodes, rank left_size + 1 belongs to the node itself. A smaller rank must be in the left subtree; a larger rank must be in the right subtree after subtracting left_size + 1.

The stored counts let each query follow only one root-to-leaf path, so a query takes O(h) time instead of starting a fresh traversal. Building all counts costs O(n) time and O(h) traversal space. The tradeoff is extra metadata and the need to keep every count correct when the tree changes.

What changes when insertions and deletions are frequent?

Use a self-balancing binary search tree whose nodes store subtree sizes. Rotations preserve search order, and the implementation recomputes the affected sizes after each structural change. The rank-selection logic from the previous follow-up then remains valid.

Balance keeps the height at O(log n), giving O(log n) rank queries, insertions, and deletions. This is the standard order-statistic-tree design. It is much more complex than the one-query traversal, so it is worthwhile only when updates and queries are both part of the workload.

Can you solve it with constant auxiliary space?

Morris inorder traversal temporarily points each node’s inorder predecessor back to that node. Those temporary threads replace the explicit stack, allowing inorder traversal with O(1) auxiliary space.

The traversal still runs in O(n) worst-case time because each temporary edge is created and removed once. A subtle production concern is cleanup: returning immediately at the k-th node could leave temporary links in the tree. The implementation must continue long enough to remove every thread, or carefully restore outstanding links before returning. That mutation risk often makes the O(h) stack preferable unless constant space is a firm requirement.

What if the input is an ordinary binary tree rather than a BST?

Inorder traversal no longer produces sorted values, so the ordering shortcut disappears. The simplest approach collects all n values and sorts them, taking O(n log n) time and O(n) space. If k is much smaller than n, a size-k max-heap keeps only the smallest values seen so far and takes O(n log k) time with O(k) space.

An in-place selection algorithm can achieve O(n) expected time after collecting the values, but it mutates that array and has a worse worst-case bound unless a deterministic pivot strategy is used. The best choice depends on whether simplicity, memory, or worst-case guarantees matter most.

How should duplicate values be ranked if the BST permits them?

First clarify whether k counts nodes or distinct values. If every node counts, the existing traversal already works: equal values occupy consecutive positions. If only distinct values count, remember the last emitted value and advance the rank only when the current value differs.

Both variants keep the same O(n) worst-case time and O(h) stack space. For repeated queries with duplicates, subtree sizes alone are not enough for distinct-value ranks unless the tree stores values in consolidated nodes with multiplicities or maintains richer distinct-count metadata.