L45: K-th Smallest / Largest Element in BST

1. Problem Statement & Overview

When working with Binary Search Trees (BSTs), a common algorithmic challenge is finding the K-th smallest or K-th largest element. Given the root of a BST and an integer $K$ , our goal is to efficiently retrieve the value of the node that would occupy the $K$ -th position if all elements of the tree were arranged in ascending sorted order.

2. The Naive Approach: Traverse, Store, and Sort

The most straightforward and intuitive way to approach this problem is to treat the BST as an unorganized collection of nodes, extract them, and sort them.

Step-by-Step Naive Workflow

Perform any standard Depth-First Search (DFS) traversal (Pre-order, Post-order, or In-order).
Push every visited node's value into a linear container (e.g., a vector in C++ or a List in Java).
Sort that container in ascending order.
Access and return the element at index $K - 1$ (since arrays/vectors are 0-indexed).

Complexity Breakdown of the Naive Approach

Time Complexity: $\mathcal{O}(N)$ for the DFS traversal, plus $\mathcal{O}(N \log N)$ to sort the container of $N$ elements, resulting in a total time complexity of $\mathcal{O}(N \log N)$ .
Space Complexity: $\mathcal{O}(N)$ to store all $N$ nodes inside an external container.

Note: While this approach works, it fails to leverage the intrinsic structural properties of a Binary Search Tree. We can eliminate the $\mathcal{O}(N \log N)$ sorting overhead entirely.

3. Core Mental Model: The BST In-Order Property

To design an optimal solution, we must remember the fundamental invariant of a Binary Search Tree:

For any given node, everything in its left subtree contains values strictly smaller than the node.
Everything in its right subtree contains values strictly greater than the node.

Real-Life Analogy

Real-Life Analogy: Imagine organizing an unorganized archive of books by always placing books with lower serial numbers to the left and higher serial numbers to the right on every shelf. If you systematically walk through the archive by visiting the leftmost (lowest) available item first, then looking at the current shelf marker, and finally examining the right side, you will inspect every single book in a strictly ascending, perfectly sorted sequence without needing to resort anything.

Because of this BST property, performing an In-order traversal (Left $\rightarrow$ Root $\rightarrow$ Right) on a BST always visits the nodes in ascending sorted order.

For example, given a BST containing elements scattered across nodes, its In-order traversal yields:

Structure & Concept Flow

In-order Sequence: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

Because the In-order traversal is inherently sorted, the $K$ -th element visited during an In-order traversal is guaranteed to be the $K$ -th smallest element in the entire BST.

4. Eliminating Sorting: Optimized In-Order Traversal

By performing an In-order traversal, we completely eliminate the $\mathcal{O}(N \log N)$ sorting step.

How the Counter Strategy Works

Instead of storing all nodes in an external array and picking the $K$ -th element at the end, we can track our position on-the-fly during the traversal using a counter:

Initialize a counter variable to 0.
Begin a standard In-order traversal (Recursive, Iterative with a Stack, or Morris Traversal).
The exact moment we "visit" a node (when processing the Root step between Left and Right), increment our counter: counter++.
Check if counter == K. If this condition evaluates to true, the node we are currently standing at is our target answer. We can immediately capture it and halt or return.

5. Space-Time Tradeoffs of Traversal Strategies

Depending on how we implement the In-order traversal, our space and time complexities vary significantly.

Traversal Strategy	Time Complexity	Auxiliary Space Complexity	Rationale / Notes
Recursive In-order	$\mathcal{O}(N)$	$\mathcal{O}(H)$ (up to $\mathcal{O}(N)$ )	Uses the system call stack. Space depends on the height ( $H$ ) of the tree.
Iterative Stack In-order	$\mathcal{O}(N)$	$\mathcal{O}(H)$ (up to $\mathcal{O}(N)$ )	Explicitly manages an auxiliary stack to simulate recursion.
Morris Traversal	$\mathcal{O}(N)$	$\mathcal{O}(1)$	Uses threaded binary tree pointers, requiring zero extra space.

6. Extending the Logic: Finding the K-th Largest Element

What if the interviewer inverts the question and asks for the K-th largest element in the BST instead of the $K$ -th smallest?

Mathematical Reduction

If a BST has a total of $N$ nodes, finding the K-th largest element from the end is equivalent to finding the $(N - K + 1)$ -th smallest element from the front (or $N - K$ using 0-based counting logic).
Therefore, we can solve this in two simple passes:
1. First Pass: Traverse the tree to count the total number of nodes ( $N$ ).
2. Second Pass: Run our optimized In-order search looking for the $(N - K)$ -th smallest element.

7. Summary and Key Takeaways

Leverage BST Properties: The defining characteristic of a BST is that its In-order traversal (Left $\rightarrow$ Root $\rightarrow$ Right) naturally produces a sorted sequence.
Avoid Naive Sorting: Storing all nodes in a list and sorting them takes $\mathcal{O}(N \log N)$ time and $\mathcal{O}(N)$ space, which is suboptimal.
On-The-Fly Counting: By incrementing a running counter precisely when visiting a node during an In-order traversal, we can spot the $K$ -th element instantly.
Optimal Space Complexity: Utilizing Morris Traversal allows us to find the $K$ -th smallest element in $\mathcal{O}(N)$ time with $\mathcal{O}(1)$ constant auxiliary space.
K-th Largest Conversion: The $K$ -th largest element in a BST of size $N$ can be efficiently mapped to finding the $(N - K)$ -th smallest element.