Minimum Distance Between BST Nodes
Last Updated: March 29, 2026
Understanding the Problem
We need to find the smallest absolute difference between the values of any two distinct nodes in a BST. At first glance, you might think about checking every pair of nodes, but the BST property gives us a much better approach.
Here is the key insight: in a BST, an inorder traversal visits nodes in ascending sorted order. When values are sorted, the minimum difference between any two elements must occur between consecutive elements. Think about it. If you have sorted values [1, 3, 6, 10], the minimum gap is between 1 and 3 (difference of 2). You would never find a smaller gap between non-consecutive elements like 1 and 10. So the problem reduces to finding the minimum difference between consecutive values in the inorder sequence.
Key Constraints:
2 <= number of nodes <= 100→ The tree is very small. Even an O(n^2) brute force checking all pairs would handle 100 nodes in microseconds. But the problem is really testing whether you understand the BST inorder property.0 <= Node.val <= 10^5→ Node values are non-negative integers. No overflow concerns with simple subtraction.- The tree is guaranteed to be a valid BST, so inorder traversal will produce a sorted sequence. This is the property we should exploit.
Approach 1: Inorder Traversal with Sorting
Intuition
The most natural first approach is to collect all the values from the BST, sort them, and then scan for the minimum gap between consecutive elements. Since it is a BST, inorder traversal already gives us sorted order, but even if you forget that property and just collect values in any order, sorting them afterwards still works.
This approach treats the BST like any other tree. Gather all values, sort them, and compare neighbors. Simple and correct.
Algorithm
- Traverse the entire BST (any traversal order works) and collect all node values into a list.
- Sort the list in ascending order.
- Iterate through the sorted list and compute the difference between each pair of consecutive elements.
- Return the minimum difference found.
Example Walkthrough
Input:
After collecting and sorting: values = [1, 2, 3, 4, 6]
Scan consecutive pairs: (1,2)=1, (2,3)=1, (3,4)=1, (4,6)=2. Minimum difference = 1.
Code
- Time Complexity: O(n log n). We visit all n nodes to collect values (O(n)), then sort them (O(n log n)). The sort dominates.
- Space Complexity: O(n). We store all n values in a list, plus the recursion stack which is O(h).
We are sorting the collected values at O(n log n), but a BST already has its values in sorted order. What if we traversed the BST in order and collected values that are already sorted?
Approach 2: Inorder Traversal into List
Intuition
Since a BST's inorder traversal naturally produces values in sorted order, we can skip the explicit sort. Just do an inorder traversal (left, root, right), collect the values, and then scan consecutive pairs for the minimum difference.
This leverages the BST property directly. The values come out sorted, so we just need one pass through the resulting list to find the smallest gap.
The BST property guarantees that inorder traversal produces a sorted sequence. And in any sorted sequence, the minimum absolute difference always occurs between adjacent elements. If you have three sorted values a < b < c, then (c - a) = (c - b) + (b - a). Both (c - b) and (b - a) are positive, so (c - a) is always larger than either of them. This means you never need to compare non-adjacent elements.
Algorithm
- Perform an inorder traversal of the BST to collect all values into a list (they will be in ascending order).
- Iterate through the list from index 1 onward, computing the difference between each element and its predecessor.
- Track and return the minimum difference.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once during inorder traversal, and then scan the list once. Both passes are O(n).
- Space Complexity: O(n). We store all n values in a list. The recursion stack adds O(h) where h is the tree height, but the list dominates.
We are storing all n values in a list just to compare consecutive pairs. What if we tracked just the previous value during the traversal and computed differences on the fly?
Approach 3: Inorder Traversal with Previous Pointer (Optimal)
Intuition
Instead of collecting all values and comparing afterwards, we can compute the minimum difference during the inorder traversal itself. We just need to remember the previously visited node's value. Each time we visit a new node in inorder sequence, we compare it with the previous value, update the minimum difference, and then move the previous pointer forward.
This is the cleanest solution. One pass, constant extra space (ignoring the recursion stack), and it directly exploits the BST property.
Algorithm
- Initialize
prevto null (or -1) andminDiffto infinity. - Perform an inorder traversal of the BST.
- At each node, if
previs set, computecurrent.val - prevand updateminDiffif this difference is smaller. - Set
prevtocurrent.valbefore moving to the next node. - After the traversal completes, return
minDiff.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each of the n nodes exactly once during the inorder traversal.
- Space Complexity: O(h). Where h is the height of the tree, due to the recursion stack. For a balanced BST, h = O(log n). For a skewed tree, h = O(n). The auxiliary space beyond the stack is O(1).