Find Kth Smallest and Largest in BST
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 1
- Core for
- 2 roles
The problem
Given the root of a binary search tree and an integer k, return both the kth smallest and kth largest elements in the tree as a pair.
Example 1
- Input
- root=[5,3,6,2,4,null,null,1], k=2
- Output
- [2, 5]
- Why
- Inorder: 1,2,3,4,5,6. 2nd smallest=2, 2nd largest=5.
Example 2
- Input
- root=[3,1,4,null,2], k=1
- Output
- [1, 4]
- Why
- Inorder: 1,2,3,4. 1st smallest=1, 1st largest=4.
Example 3
- Input
- root=[2,1,3], k=3
- Output
- [3, 1]
- Why
- Inorder: 1,2,3. 3rd smallest=3, 3rd largest=1.
Constraints
- The number of nodes is in the range [1, 104].
- 0 <= Node.val <= 104
- 1 <= k <= the number of nodes.
How to think about it
Updated 2026-09-09The BST property gives sorted ordering in both directions: ascending via inorder (left-root-right) and descending via reverse inorder (right-root-left). Finding both elements comes down to two coordinated walks, or a single inorder pass that records the kth element from the front and the kth element from the back.
Approaches, worst first
Full traversal into array
time O(n) · space O(n)
Perform a full inorder traversal collecting all values into an array of size n. Read the kth smallest at index `k - 1` and the kth largest at index `n - k`. Works reliably but buffers all n nodes regardless of k.
Dual early-stopping traversalsWrite this one
time O(h + k) · space O(h)
Run an iterative inorder traversal stopping at step k to obtain the kth smallest, followed by a reverse inorder traversal stopping at step k to obtain the kth largest. Visits only the necessary nodes for each query.
Where people lose marks · 2
- Index mapping when reading from collected array: the kth smallest is at index `k - 1` while the kth largest is at `n - k`; mixing up 0-based and 1-based indexing causes off-by-one errors.
- Overlapping counters when running recursive traversals: counter variables must be reset or scoped independently between the forward and reverse passes.
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .