Minimum Absolute Difference in BST
Minimum Absolute Difference in BST: find the smallest absolute difference between the values of any two different nodes in a binary search tree.
- The number of nodes in the tree is in the range [2, 10⁴]
- 0 <= Node.val <= 10⁵
- The tree is a valid binary search tree
Intuition
In a BST an inorder traversal visits values in sorted order, and in a sorted sequence the closest pair is always adjacent — two values with anything between them are further apart than either is from what separates them. So the answer is the smallest gap between consecutive inorder values, found by walking the tree once while remembering only the previously visited value.
Whenever a BST question asks about ordering, rank, or closeness of values, inorder traversal is the move — it turns the tree into a sorted sequence for free. Kth Smallest Element in a BST and Validate Binary Search Tree both rely on the same property.
Approach
Before reading on: prove to yourself that a non-adjacent pair in sorted order can never give the minimum difference. Then decide what single piece of state the traversal must carry to avoid building a list of values.
Why only adjacent pairs need checking
Sort the values as v₁ < v₂ < … < vₙ. For any i < j with j > i + 1, the difference vⱼ - vᵢ equals the sum of all the consecutive gaps between them, and since every gap is positive that sum exceeds any single gap it contains. So a non-adjacent pair can never be the minimum. This reduces the candidate set from the O(n²) pairs to the n - 1 adjacent ones, and it is the reason the problem is linear rather than quadratic.
Inorder traversal is the sort
The BST property says every value in a node's left subtree is smaller and every value in its right subtree is larger. Visiting left subtree, then node, then right subtree therefore emits values in ascending order without any sorting step. Crucially the tree must not be flattened into a list first — that would cost O(n) extra space for no benefit. Carrying a single prev variable across the recursion gives the same information, because the traversal only ever needs the value visited immediately before the current one.
Threading prev through the recursion
Keep prev and best outside the recursive helper — as instance attributes, a closure, or a nonlocal binding. At each node, if prev is not None, update best = min(best, node.val - prev); then set prev = node.val before descending right. The subtraction needs no abs because inorder order guarantees node.val >= prev. The update must happen between the two recursive calls, not before or after both, or the values are compared out of order and the invariant collapses. Time is O(n), space O(h) for the call stack.
Solution & live demo
Common pitfalls
Comparing all pairs of nodes
for a in values:
for b in values:
if a != b:
best = min(best, abs(a - b))compare only inorder-adjacent values
This is O(n²) and ignores the BST structure entirely. With 10⁴ nodes it performs a hundred million comparisons to find something a single ordered walk gets in ten thousand.
Updating prev before recursing left
self.prev = node.val inorder(node.left) inorder(node.right)
inorder(node.left) # compare, then self.prev = node.val inorder(node.right)
The node must be visited between its two subtrees. Assigning prev first compares the node against its own left descendants in the wrong order, breaking the ascending invariant the whole method depends on.
Assuming the root holds the closest pair
return min(root.val - root.left.val, root.right.val - root.val)
traverse the entire tree in order
The closest pair can sit anywhere, often deep inside one subtree. Only a full inorder walk sees every adjacent pair, and skipping any of them can miss the true minimum.
Edge cases
One adjacent pair exists, and its difference is the answer.
Inorder still yields ascending order; the recursion depth reaches n.
Only inorder-adjacent pairs are compared, so the true minimum is still found.
The minimum difference is 1, which no pair can beat given distinct values.
prev is None, so no comparison is made and only the assignment runs.