Smallest Absolute Difference in a BST
Problem
Given a BST, find the smallest absolute difference between any two distinct node values.
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.
Input
level-order: [4, 2, 6, 1, 3]Output
1In-order = 1, 2, 3, 4, 6 — smallest gap is 1.
def min_diff(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 minDiff(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);
}