Minimum Distance Between BST Nodes
Understanding the Problem
We need to find the smallest absolute difference between the values of any two distinct nodes in a BST. Checking every pair of nodes works, but the BST property leads to a faster approach.
An inorder traversal of a BST visits nodes in ascending sorted order. In a sorted sequence, the minimum difference between any two elements always occurs between consecutive elements. Take the sorted values [1, 3, 6, 10]: the smallest gap is between 1 and 3 (a difference of 2), and no non-consecutive pair like 1 and 10 can produce a smaller gap. 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 small, so even an O(n^2) brute force over all pairs would finish quickly. The interesting solution exploits the BST inorder property.0 <= Node.val <= 10^5→ Values are non-negative integers, and the maximum gap fits in a 32-bit int, so subtraction never overflows.- The tree is a valid BST, so inorder traversal produces a sorted sequence.
Approach 1: Inorder Traversal with Sorting
Intuition
Collect all the values from the BST, sort them, then scan for the minimum gap between consecutive elements. This treats the BST like any other binary tree: the traversal order does not matter because the explicit sort puts the values in order regardless.
This is a useful baseline because it works on any binary tree, not only a BST. The later approaches improve on it by using the BST property to avoid the sort.
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 uses 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).