Minimum Absolute Difference in BST
Problem
root of a binary search tree with at least
two nodes. Among all pairs of different nodes, find the smallest absolute
difference between their values and return it.root = [4,2,6,1,3]Output1root = [1,0,48,null,null,12,49]Output1root = [10,null,90]Output802 ≤ nodes ≤ 104 · 0 ≤ Node.val ≤ 105
Try it yourself
class Solution {
public int getMinimumDifference(TreeNode root) {
}
}
Instinct The tree is a BST? Its in-order walk is a sorted list and every node splits the search space - think "sorted array in tree form", not "visit everything".
Memory hack Left is less, right is more, in-order reads the sorted score - and every node lives inside a (low, high) fence set by its ancestors.
Open the Binary Search Tree & In-order guide →Approaches
Brute ForceCollect Values, Check Every Pair
O(n²)Space O(n)Gather all values with any traversal, then compare each pair
(i, j) and keep the smallest |a − b|. It never uses
the BST ordering, so every pair has to be inspected.
public int getMinimumDifference(TreeNode root) { List<Integer> vals = new ArrayList<>(); collect(root, vals); int best = Integer.MAX_VALUE; for (int i = 0; i < vals.size(); i++) for (int j = i + 1; j < vals.size(); j++) best = Math.min(best, Math.abs(vals.get(i) - vals.get(j))); return best; } private void collect(TreeNode node, List<Integer> vals) { if (node == null) return; vals.add(node.val); collect(node.left, vals); collect(node.right, vals); }
Obviously correct, but quadratic: 104 nodes means ~5·107 pairs.
BetterIn-order List + Adjacent Gaps
O(n)Space O(n)Do the traversal in-order instead, which yields the values already
sorted — no sort needed. The minimum gap of a sorted list is among neighbouring
elements, so a single scan over vals[i] − vals[i-1] finishes it.
public int getMinimumDifference(TreeNode root) { List<Integer> sorted = new ArrayList<>(); inorder(root, sorted); int best = Integer.MAX_VALUE; for (int i = 1; i < sorted.size(); i++) best = Math.min(best, sorted.get(i) - sorted.get(i - 1)); // already ascending return best; } private void inorder(TreeNode node, List<Integer> out) { if (node == null) return; inorder(node.left, out); out.add(node.val); inorder(node.right, out); }
Linear time, but stores every value just to look at neighbours.
OptimalIn-order with a Previous Pointer
O(n)Space O(h)Fuse the scan into the traversal. Keep prev, the value visited
just before the current node in sorted order; at each node update the answer with
node.val − prev and then move prev forward. Only the
recursion stack remains.
private Integer prev; // previous value in in-order (sorted) order private int best; public int getMinimumDifference(TreeNode root) { prev = null; best = Integer.MAX_VALUE; inorder(root); return best; } private void inorder(TreeNode node) { if (node == null) return; inorder(node.left); if (prev != null) best = Math.min(best, node.val - prev); prev = node.val; inorder(node.right); }
One pass, no list — the standard “sorted neighbours in a BST” trick.
Integer (null) for “no previous value yet” avoids
sentinel tricks like prev = -∞ that can overflow.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Collect Values, Check Every Pair | O(n²) | O(n) |
| Better | In-order List + Adjacent Gaps | O(n) | O(n) |
| Optimal | In-order with a Previous Pointer | O(n) | O(h) |
- Comparing each node only with its own children — the closest value can be far away in the tree (e.g. root vs. a deep leaf).
- Initialising
prevto a sentinel likeInteger.MIN_VALUEand subtracting → overflow. - Keeping
prevas a method parameter: it must carry over between subtrees, so use a field or a holder.
- Say the key fact out loud: in-order of a BST is sorted, and the minimum gap lies between neighbours.
- Point out the O(n) list version first, then remove the list.
- Mention Morris traversal if asked for O(1) extra space.