DSA AnimatorDSA animations
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.

How to solve Kth Smallest Element in a BST

LeetCode 230 · Medium · Tree · Pattern: Inorder Counting

Why the obvious approach is slow

You could copy every value into an array, sort it, and pick index k −1. But a search tree already gives sorted order through an inorder traversal. And we can stop as soon as we reach the k-th value.

The key idea

Inorder visits left, then the node, then right. In a search tree, that means values come out from smallest to largest. Count each node as it is visited. When the count reaches k, that node is the answer, and you can stop.

Remember

Inorder of a search tree is sorted. Stop early as soon as you have counted k nodes.

Run the animation above on your own input, or watch the 1:49 video explanation of Kth Smallest Element in a BST with a dry run and Java code.

More Tree problems