Querying a BST

The problem

Your BST holds ten thousand exam scores. Now the questions get harder than "is 87 present?" A teacher asks for the 3rd lowest score. A dashboard wants every score between 60 and 70. A fraud check wants to know if two scores sum to exactly 150. These aren't membership tests — they're questions about order and range.

You could dump every key into an array, sort it, and answer from there. But you already paid to keep the tree sorted. Flattening and re-sorting on every query throws that away and drags each answer toward O(n log n). The tree should be able to answer ordered questions directly.

A first attempt

The brute-force route: do an in-order traversal into a list (that list is already sorted), then solve on the array — index k-1 for the kth smallest, a linear scan for the range, two pointers for the pair-sum.

That works and it's O(n) time with O(n) extra space for the array. But it ignores what the tree gives you. For "kth smallest" you don't need the whole array — you can stop the moment you've counted k nodes. For a range query you can skip entire subtrees that fall outside the bounds. The array approach visits everything; the tree lets you visit only what matters.

The insight

An in-order traversal of a BST yields keys in ascending order — and you can steer that walk using the ordering to prune.

• kth smallest: walk in order, counting. The kth node you visit is the answer, so stop there instead of finishing the tree.
• Range [lo, hi]: at each node, only recurse left when node.key > lo, only recurse right when node.key < hi. Whole subtrees outside the range never get visited.
• Pair with sum = target: an in-order walk gives a sorted stream, so the classic two-pointer trick applies — advance from both ends of the sorted order toward each other.

The tree isn't just storage; its shape is an index on order.

How it works

Counting to the 3rd smallest in this tree visits 1, 3, 4 and stops — it never touches the right subtree:

          8
        /   \
       3      10
      / \       \
     1   6       14
        / \
       4   7

in-order: 1  3  4  6  7  8  10  14
             └────┘
          3rd smallest = 4

The code

The kth smallest query, shown iteratively with an explicit stack.

def kth_smallest(root, k):
    stack = []
    node = root
    while stack or node is not None:
        while node is not None:      # dive to the leftmost
            stack.append(node)
            node = node.left
        node = stack.pop()           # visit in ascending order
        k -= 1
        if k == 0:
            return node.key
        node = node.right
    return None  # k larger than tree size

function kthSmallest(root: Node | null, k: number): number | null {
  const stack: Node[] = [];
  let node = root;
  while (stack.length > 0 || node !== null) {
    while (node !== null) {          // dive to the leftmost
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;             // visit in ascending order
    k -= 1;
    if (k === 0) return node.key;
    node = node.right;
  }
  return null; // k larger than tree size
}

Integer kthSmallest(Node root, int k) {
    Deque<Node> stack = new ArrayDeque<>();
    Node node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {       // dive to the leftmost
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();          // visit in ascending order
        if (--k == 0) return node.key;
        node = node.right;
    }
    return null; // k larger than tree size
}

#include <stdlib.h>

int kth_smallest(struct Node *root, int k, int *found) {
    struct Node *stack[256];
    int top = 0;
    struct Node *node = root;
    while (top > 0 || node != NULL) {
        while (node != NULL) {       /* dive to the leftmost */
            stack[top++] = node;
            node = node->left;
        }
        node = stack[--top];         /* visit in ascending order */
        if (--k == 0) { *found = 1; return node->key; }
        node = node->right;
    }
    *found = 0;
    return -1; /* k larger than tree size */
}

#include <stack>
#include <optional>

std::optional<int> kthSmallest(Node *root, int k) {
    std::stack<Node *> stk;
    Node *node = root;
    while (!stk.empty() || node != nullptr) {
        while (node != nullptr) {    // dive to the leftmost
            stk.push(node);
            node = node->left;
        }
        node = stk.top();            // visit in ascending order
        stk.pop();
        if (--k == 0) return node->key;
        node = node->right;
    }
    return std::nullopt; // k larger than tree size
}

Complexity

h is the tree height. The kth-smallest walk touches only the first k visited nodes plus the O(h) descent to reach them; the range query pays only for the descent plus the m keys it actually reports.

When to use it

Practice

Recap

• Every ordered query rides on the fact that in-order traversal yields sorted keys.
• Steer the walk with the BST ordering to prune: stop early for kth-smallest, skip out-of-range subtrees for range queries.
• Augmenting nodes with subtree size turns rank/kth-smallest queries into pure O(h).