401. Minimum Absolute Difference in BST
You receive root, the root node of a binary search tree holding at least two nodes with distinct non-negative values. Return the smallest absolute difference |a − b| over every pair of distinct node values a and b in the tree.
The pair achieving the minimum does not have to be a parent and child — the two closest values can live in completely different subtrees. The BST ordering is the tool that keeps you from comparing all pairs.
Example 1:
Input: root = [4, 2, 6, 1, 3]
Output: 1
Explanation: The values are {1, 2, 3, 4, 6}. The closest pairs are (1, 2), (2, 3), and (3, 4), each 1 apart — note that 3 and 4 sit in different parts of the tree.
Example 2:
Input: root = [1, 0, 48, null, null, 12, 49]
Output: 1
Explanation: Sorted, the values read 0, 1, 12, 48, 49. Both (0, 1) and (48, 49) are 1 apart, so the answer is 1.
Constraints:
- 2 ≤ number of nodes ≤ 10⁴
- 0 ≤ node value ≤ 10⁵
- All node values are distinct
- The tree is a valid binary search tree
Hints:
The two closest values in any set of numbers are neighbors once the set is sorted — no need to compare every pair. What traversal of a BST hands you the values already in sorted order?
An inorder traversal (left, node, right) of a BST visits values in increasing order. Carry the previously visited value along and take value − prev at each node; the smallest such gap is the answer, with no extra array or sort.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [4, 2, 6, 1, 3]
Expected output: 1