Pattern this teaches:Binary Search Tree Problems
Kth Smallest Element in a BST
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 2
- Core for
- 2 roles
The problem
In a binary search tree, list the values from smallest to largest and return the one at position k, counting from 1. Reading the tree in inorder visits its values in exactly that sorted order.
Example 1
- Input
- root=[6,3,8,null,5], k=1
- Output
- 3
- Why
- Inorder order is 3,5,6,8: the smallest is 3.
Example 2
- Input
- root=[9,6,11,4,7,null,null,2], k=3
- Output
- 6
- Why
- Inorder order is 2,4,6,7,9,11: the 3rd smallest is 6.
Example 3
- Input
- root=[1,null,2], k=2
- Output
- 2
- Why
- Inorder traversal is 1,2. The 2nd smallest element is 2.
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-29The BST property makes an inorder traversal visit nodes in strictly ascending order. Finding the kth smallest element does not require sorting or inspecting every node: it is the kth element emitted by an inorder sequence, which can halt the exact instant the count hits k.
Approaches, worst first
Full traversal into array
time O(n) · space O(n)
Dump the entire inorder traversal into a list and index element k - 1. Trivial to write, but it exhausts O(n) memory and traverses all n nodes even when k is 1.
Early-stopping iterative inorder
time O(h + k) · space O(h)
Push left children onto an explicit stack. When popping, decrement k; when k reaches 0, return the popped node value immediately without visiting the remainder of the tree. Stops early after visiting exactly k nodes.
Morris inorder traversalWrite this one
time O(n) · space O(1)
Thread temporary links from each node's inorder predecessor to the node itself, allowing inorder traversal without recursion or an explicit stack. Decrement k when visiting, and clean up temporary threads before returning.
Where people lose marks · 2
- One-based indexing confusion. Forgetting to stop when k hits 0 or indexing arr[k] instead of arr[k - 1] off-by-ones the result.
- Failing to clean up threaded pointers in Morris traversal if returning early on k == 0; leaving cycle pointers corrupts the underlying tree.
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 .