#530 Minimum Absolute Difference in BST

frequently reported atGoogle Amazon

the problem

In plain words

Given the root of a BST with at least two nodes, return the smallest difference between the values of any two different nodes.

in root = [4,2,6,1,3]

out 1

Sorted values 1, 2, 3, 4, 6: neighbours differ by 1, 1, 1, 2.

in root = [1,0,48,null,null,12,49]

out 1

48 and 49.

2 ≤ number of nodes ≤ 10⁴
0 ≤ Node.val ≤ 10⁵
Same problem as LC 783 (Minimum Distance Between BST Nodes)

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBST property

In a sorted list, the closest pair always sits side by side. Inorder gives you the BST's values sorted — so compare each value only with the one just before it.

solutions

From brute force to optimal

Ignore the order: collect all values and compare each pair.

Collect values in any traversal.
For every pair i < j, best = min(best, |a[i] − a[j]|).

timeO(n²)

n(n − 1)/2 pairs — about 5·10⁷ for n = 10⁴.

spaceO(n)

The list of values.

javajava.util.*

1class Solution {2    /** Ignores the BST order: compare every pair of values. */3    public int getMinimumDifference(TreeNode root) {4        List<Integer> values = new ArrayList<>();5        collect(root, values);6        int best = Integer.MAX_VALUE;7        for (int i = 0; i < values.size(); i++)8            for (int j = i + 1; j < values.size(); j++)9                best = Math.min(best, Math.abs(values.get(i) - values.get(j)));10        return best;11    }12 13    private void collect(TreeNode node, List<Integer> out) {14        if (node == null) return;15        out.add(node.val);16        collect(node.left, out);17        collect(node.right, out);18    }19}

Inorder gives sorted values; check adjacent differences.

Inorder into a list.
best = min over i of list[i] − list[i − 1].

timeO(n)

One traversal plus one scan.

spaceO(n)

The list.

javajava.util.*

1class Solution {2    /** Inorder gives the values sorted, and the closest pair in a sorted list sits side by side. */3    public int getMinimumDifference(TreeNode root) {4        List<Integer> sorted = new ArrayList<>();5        inorder(root, sorted);6        int best = Integer.MAX_VALUE;7        for (int i = 1; i < sorted.size(); i++) best = Math.min(best, sorted.get(i) - sorted.get(i - 1));8        return best;9    }10 11    private void inorder(TreeNode node, List<Integer> out) {12        if (node == null) return;13        inorder(node.left, out);14        out.add(node.val);15        inorder(node.right, out);16    }17}

Same comparison, but remember only the previous value while walking.

prev = null, best = MAX.
Inorder: at each node, if prev != null, best = min(best, node.val − prev).
prev = node.val.

timeO(n)

Each node visited once.

spaceO(h)

Only the recursion stack; no list.

javajava.util.*

1class Solution {2    private int best;3    private Integer prev;   // the value visited just before, in sorted order (null at the start)4 5    public int getMinimumDifference(TreeNode root) {6        best = Integer.MAX_VALUE;7        prev = null;8        inorder(root);9        return best;10    }11 12    private void inorder(TreeNode node) {13        if (node == null) return;14        inorder(node.left);15        if (prev != null) best = Math.min(best, node.val - prev);   // sorted, so node.val > prev16        prev = node.val;17        inorder(node.right);18    }19}

in the room

How to say it in the interview

talk track

Start from "inorder of a BST is sorted" — then it's the classic "closest pair in a sorted array".
Mention why node.val − prev needs no Math.abs: inorder guarantees node.val > prev.

traps

Comparing each node only with its children — the closest pair can be a node and a deep descendant (the root and the rightmost node of its left subtree).
Keeping prev and best as fields without resetting them at the start of each call.

what they ask next

Follow-ups

Two Sum IV - Input is a BST (LC 653)?

Same sorted view: run an ascending and a descending BST iterator as two pointers — O(n) time, O(h) space.

before you submit

Edge cases to test

Exactly two nodes → their difference.
The closest pair is a node and a far descendant, not a parent and child.
The same Solution object called twice → reset prev and best inside the method.

practise next