265. Minimum Absolute Difference in BST

An in-order traversal of a BST visits values in sorted order, so the closest pair must be adjacent in that sequence. Track the previous value and take the smallest gap between consecutive visits.

Idea

In a BST, an in-order traversal (left, node, right) yields the node values in ascending order. In a sorted sequence, the minimum absolute difference always occurs between two adjacent elements — so we never need to compare far-apart nodes. Keep the previously visited value and minimize the gap as we go.

Algorithm

1. Traverse the tree in-order, keeping prev (the last value seen) and best (∞).
2. At each node, if prev exists, update best = min(best, node.val - prev).
3. Set prev = node.val and continue.
4. Return best.

Worked example: [4,2,6,1,3]

      4
     / \
    2   6
   / \
  1   3

In-order sequence: 1, 2, 3, 4, 6. Adjacent gaps: 1, 1, 1, 2. The minimum is 1.

Complexity

• Time: O(n) — each node visited once.
• Space: O(h) for the traversal stack/recursion.

class Solution {
    private Integer prev = null;
    private int best = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        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);
    }
}