#530
Minimum Absolute Difference in BST
Easy Inorder = sorted
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the smallest difference between the values of any two nodes in a BST.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the smallest difference between any two values.
Why this works: inorder gives sorted values; the closest pair is always neighbours in sorted order.
Example: 4 (2 (1, 3), 6)
inorder 1, 2, 3, 4, 6 → gaps 1, 1, 1, 2 → 1✦Hints open one at a time
An inorder traversal of a BST visits values in sorted order.
In a sorted list, the minimum difference is between neighbours.
↗Approach
Inorder traversal remembering the previous value; update the best with current − previous.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
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 n) {
if (n == null) return;
inorder(n.left);
if (prev != null) best = Math.min(best, n.val - prev); // neighbours in sorted order
prev = n.val;
inorder(n.right);
}
}!Common mistake
Only comparing a node with its direct children — the closest value can be far away in the tree.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon