Minimum Absolute Difference in BST — Problem & Solution
Minimum Absolute Difference in BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Absolute Difference in BST is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary search tree with distinct values, return the minimum absolute difference between the values of any two different nodes.
Example 1
Input: root = [4,2,6,1,3]
Output: 1
Explanation: Several pairs differ by 1, for example 1 and 2, or 3 and 4.
Example 2
Input: root = [1,0,48,null,null,12,49]
Output: 1
Explanation: Inorder the values are 0, 1, 12, 48, 49; both 0 and 1 and 48 and 49 differ by 1.
Example 3
Input: root = [10,null,100000]
Output: 99990
Constraints
The number of nodes in the tree is in the range [2, 10^4]0 <= Node.val <= 10^5All values are distinct
Hints for Minimum Absolute Difference in BST
Hint 1
In sorted order, the closest pair of numbers is always a pair of neighbours.
Hint 2
An inorder walk of a BST lists its values in sorted order.
Hint 3
So walk inorder, remembering only the previous value, and take the smallest gap between consecutive values.
How to solve Minimum Absolute Difference in BST
Sorted order puts the closest two values next to each other, and inorder traversal of a BST is sorted order. One inorder pass comparing each value with the one before it finds the answer.
Approach
- Walk the BST inorder, keeping the previously visited value (none at the start).
- At each node, if there is a previous value, update
best = min(best, val - prev). - Set
prev = valand continue. - Return
best.
Why it works
For sorted values a1 < a2 < … < an, any pair ai < aj with a gap of more than one position has aj - ai >= a(i+1) - ai, so some adjacent pair is at least as close. Inorder visits exactly the sorted sequence, so its consecutive differences include the minimum.
Complexity
- Time —
O(n) - Space —
O(h) for the traversal
Pitfalls
- Comparing only parents with children is not enough: in the first example 3 and 4 differ by 1, yet 3 is a grandchild of 4.
- Values start at 0, so do not use 0 as a 'no previous value' marker.
Reference solution
Python
from typing import Optional
def getMinimumDifference(root: Optional[TreeNode]) -> int:
best = float("inf")
prev = None
stack = []
cur = root
while cur is not None or stack:
while cur is not None:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if prev is not None:
best = min(best, cur.val - prev)
prev = cur.val
cur = cur.right
return int(best)Java
public static int getMinimumDifference(TreeNode root) {
int best = Integer.MAX_VALUE, prev = -1;
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (prev >= 0) best = Math.min(best, cur.val - prev);
prev = cur.val;
cur = cur.right;
}
return best;
}C++
int getMinimumDifference(TreeNode* root) {
int best = INT_MAX, prev = -1;
vector<TreeNode*> stack;
TreeNode* cur = root;
while (cur || !stack.empty()) {
while (cur) {
stack.push_back(cur);
cur = cur->left;
}
cur = stack.back();
stack.pop_back();
if (prev >= 0) best = min(best, cur->val - prev);
prev = cur->val;
cur = cur->right;
}
return best;
}JavaScript
var getMinimumDifference = function(root) {
var best = Infinity, prev = null;
var stack = [], cur = root;
while (cur !== null || stack.length > 0) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (prev !== null) best = Math.min(best, cur.val - prev);
prev = cur.val;
cur = cur.right;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)