← Back to DSA Animator
Kth Smallest Element in a BST LC #230 Medium BST In-order · Counter
Problem

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: In-order = [1,2,3,4]. 1st smallest = 1.
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: In-order = [1,2,3,4,5,6]. 3rd smallest = 3.
Constraints: 1 ≤ k ≤ n ≤ 104  |  0 ≤ Node.val ≤ 104  |  Tree is a valid BST
Try Examples
Custom:
Approach
BST In-order = Sorted Order
In-order traversal of a BST visits nodes in sorted (ascending) order. Count down k as each node is visited. When count hits 0, the current node is the k-th smallest.
In-order Sequence (BST in-order = sorted ascending)
Traversal not started yet…
Binary Search Tree
Processing
Counted
Found (k-th)
Visited/Done
Variables
Current Node
—
count (k left)
—
In-order Visited
0
Result
—
DFS Recursion Stack
Stack is empty — not started
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
In-order: recurse LEFT first — BST left subtree always holds smaller values.
2
Visit current node: count[0]--. We have found one more in-order value.
3
If count[0] == 0 → found! result[0] = node.val; stop traversal.
4
Recurse RIGHT — only if result not yet found; larger values live here.
Time
O(H + k)
Space
O(H)
Key Insight: BST In-order = Sorted
Left subtree
All values < root → visited first → appear earlier in sorted order
Root
Visited after left → appears in its correct sorted position
Right subtree
All values > root → visited last → appear later in sorted order

By counting as we go (decrementing from k to 0), we avoid building the full sorted list. We stop as soon as the k-th node is reached — making it O(H+k) instead of O(n).

Why In-order Works on a BST

A BST's core property: every node in the left subtree is smaller, and every node in the right subtree is larger. In-order traversal (left → node → right) leverages this to visit all nodes in non-decreasing order. The first node visited is the global minimum, the second is the second smallest, and so on. Counting down from k to 0 pinpoints the k-th element without materialising the full sorted sequence. Using int[] count (a mutable array wrapper) lets the counter be shared across recursive calls in Java.