DSA problem
Minimum Absolute Difference in BST
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
This is the same exercise as "Minimum Distance Between BST Nodes" — the names differ but the algorithm is identical. The reason both exist is mostly historical: LeetCode published the easier version first, then added a follow-up under a different title. The takeaway is the BST's defining invariant gives us all the structure we need.
An inorder traversal of a BST visits node values in strictly increasing order, so the minimum absolute difference between any pair of values must occur between two values that are adjacent in that sorted sequence. Anywhere else in the sequence the gap can only grow, never shrink.
We therefore perform an inorder walk and remember a single value: the previously visited node's value. At each new node we update the running minimum with curr.val - prev (which is non-negative because the sequence is sorted) and then advance prev. This runs in O(n) time and O(h) space — there is no need to materialize the full sorted list.
Examples
root = [4,2,6,1,3]1root = [1,0,48,null,null,12,49]1root = [236,104,701,null,227,null,911]9Constraints
- The number of nodes in the tree is in the range [2, 10^4].
- 0 <= Node.val <= 10^5
- The tree is guaranteed to be a valid BST.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.