Minimum Absolute Difference in BST
Problem
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
A BST visited in-order yields values in sorted order. The minimum gap between any pair of values must be the smallest gap between consecutive values in that sorted sequence — so do an in-order DFS, keep the previous value, and take min of val − prev.
level-order: [4, 2, 6, 1, 3]1def get_minimum_difference(root):
prev = [None]; best = [float("inf")]
def visit(node):
if node is None: return
visit(node.left)
if prev[0] is not None:
best[0] = min(best[0], node.val - prev[0])
prev[0] = node.val
visit(node.right)
visit(root)
return best[0]function getMinimumDifference(root) {
let prev = null, best = Infinity;
function visit(node) {
if (!node) return;
visit(node.left);
if (prev !== null) best = Math.min(best, node.val - prev);
prev = node.val;
visit(node.right);
}
visit(root);
return best;
}class Solution {
Integer prev = null; int best = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
visit(root); return best;
}
void visit(TreeNode node) {
if (node == null) return;
visit(node.left);
if (prev != null) best = Math.min(best, node.val - prev);
prev = node.val;
visit(node.right);
}
}int prev_ = -1, best = INT_MAX;
void visit(TreeNode* node) {
if (!node) return;
visit(node->left);
if (prev_ != -1) best = min(best, node->val - prev_);
prev_ = node->val;
visit(node->right);
}Explanation
The clever observation here is that a binary search tree stores its values in sorted order if you read it the right way. So instead of comparing every pair of nodes, we only need to look at neighbors in sorted order.
An in-order traversal of a BST — go left, visit the node, go right — spits out the values from smallest to largest. The smallest gap between any two values has to be a gap between two values that are next to each other in this sorted list, so that is all we check.
As we walk in order, we keep a single variable prev holding the value of the previous node we visited. At each node we compute node.val - prev and keep the smallest such difference in best.
Example: the tree gives in-order 1, 2, 3, 4, 6. The consecutive gaps are 1, 1, 1, 2, so the smallest is 1. We never had to compare, say, 1 with 6 directly.
Because we touch each node once and only remember one previous value, this is a single clean pass over the tree.