Problem Statement
Given the root of a Binary Search Tree (BST) containing n > 1 nodes, find the minimum absolute difference between the values of any two different nodes.
Example 1
50
/ \
30 70
/ / \
20 60 80
The inorder traversal is:
20 → 30 → 50 → 60 → 70 → 80
The differences between adjacent values are:
30 - 20 = 10
50 - 30 = 20
60 - 50 = 10
70 - 60 = 10
80 - 70 = 10
Therefore, the minimum absolute difference is:
10
Key Concept
The most important property of a Binary Search Tree is:
Left subtree < Root < Right subtree
Because of this property, an inorder traversal of a BST always produces the node values in sorted order.
For example:
BST:
50
/ \
30 70
/ / \
20 60 80
Inorder:
20 → 30 → 50 → 60 → 70 → 80
Once the values are sorted, we only need to compare adjacent values.
Why?
Suppose the sorted values are:
10, 20, 25, 40
The possible differences include:
20 - 10 = 10
25 - 10 = 15
40 - 10 = 30
25 - 20 = 5
40 - 20 = 20
40 - 25 = 15
The minimum difference is 5, which is between adjacent values 20 and 25.
Therefore, instead of comparing every pair of nodes, we only compare each node with the previous node visited during inorder traversal.
Approach
We use inorder traversal with two variables:
prev→ stores the previous node's value.minDiff→ stores the minimum difference found so far.
Steps
Traverse the left subtree.
When visiting the current node:
If a previous value exists, calculate:
current value - previous value
Update
minDiff.
Store the current node's value in
prev.Traverse the right subtree.
Return
minDiff.
Java Code
class Solution {
int prev = -1;
int minDiff = Integer.MAX_VALUE;
public int absDiff(Node root) {
inorder(root);
return minDiff;
}
void inorder(Node root) {
if (root == null) {
return;
}
// Traverse left subtree
inorder(root.left);
// Compare current value with previous value
if (prev != -1) {
minDiff = Math.min(minDiff, root.data - prev);
}
// Update previous value
prev = root.data;
// Traverse right subtree
inorder(root.right);
}
}
Code Explanation
1. Variables
int prev = -1;
int minDiff = Integer.MAX_VALUE;
prev
prev stores the value of the previous node visited during inorder traversal.
Initially:
prev = -1
Since node values are given as 0 or greater, -1 can be used to indicate that there is no previous node yet.
minDiff
We initialize minDiff with the largest possible integer value:
Integer.MAX_VALUE
This allows the first calculated difference to replace it.
2. Main Function
public int absDiff(Node root) {
inorder(root);
return minDiff;
}
The absDiff() method starts the inorder traversal.
After traversal is completed, minDiff contains the smallest difference found.
3. Base Condition
if (root == null) {
return;
}
If the current node is null, there is nothing to process, so we return.
This is the stopping condition for recursion.
4. Traverse Left Subtree
inorder(root.left);
We first visit the left subtree.
This is important because inorder traversal follows:
Left → Root → Right
For a BST, this produces values in sorted order.
5. Calculate Difference
if (prev != -1) {
minDiff = Math.min(minDiff, root.data - prev);
}
After visiting the left subtree, we process the current node.
If prev contains a valid previous value, we calculate:
current value - previous value
For example:
Previous = 30
Current = 50
Difference = 50 - 30
= 20
Then:
Math.min(minDiff, 20)
keeps the smaller value.
6. Update Previous Value
prev = root.data;
After processing the current node, its value becomes the previous value for the next node.
For example:
20 → 30 → 50
When processing 30:
prev = 20
current = 30
difference = 10
After processing:
prev = 30
Then when processing 50:
prev = 30
current = 50
difference = 20
7. Traverse Right Subtree
inorder(root.right);
Finally, we visit the right subtree.
This maintains the inorder traversal:
Left → Root → Right
Dry Run
Consider:
50
/ \
30 70
/ / \
20 60 80
Inorder Traversal
The traversal produces:
20 → 30 → 50 → 60 → 70 → 80
Now let's process each value.
Current | Previous | Difference | Minimum |
|---|---|---|---|
20 | -1 | - | MAX |
30 | 20 | 10 | 10 |
50 | 30 | 20 | 10 |
60 | 50 | 10 | 10 |
70 | 60 | 10 | 10 |
80 | 70 | 10 | 10 |
Finally:
minDiff = 10
So the answer is:
10
Why Don't We Compare Every Pair?
A simple approach would be to calculate the difference between every pair of nodes.
For n nodes, there can be approximately:
n × (n - 1) / 2
pairs.
That results in:
O(n²)
time complexity.
But the BST property gives us a better solution.
Since inorder traversal already gives sorted values:
10 → 15 → 30 → 45 → 50
we only need to check:
15 - 10
30 - 15
45 - 30
50 - 45
Therefore, every node is processed only once.
Why
root.data - prev Instead of Math.abs()?Normally, absolute difference is:
Math.abs(a - b)
But here, inorder traversal gives values in increasing order.
Therefore:
current >= previous
So:
current - previous
will never be negative.
For example:
20 → 30 → 50 → 60
The differences are:
30 - 20 = 10
50 - 30 = 20
60 - 50 = 10
Thus, Math.abs() is unnecessary.
Another Example
Consider:
60
/ \
30 90
/
10
Inorder traversal:
10 → 30 → 60 → 90
Differences:
30 - 10 = 20
60 - 30 = 30
90 - 60 = 30
Therefore:
Answer = 20
Complexity Analysis
Time Complexity
O(n)
Each node is visited exactly once during inorder traversal.
Auxiliary Space
O(h)
where h is the height of the BST.
The space is used by the recursion stack.
For a balanced BST:
h = O(log n)
For a skewed BST:
h = O(n)
Therefore, the expected auxiliary space is:
O(h)
Important Interview Point
Whenever you see a problem involving minimum difference between values in a BST, remember:
Inorder traversal of a BST gives sorted values.
So the general pattern is:
BST
↓
Inorder Traversal
↓
Sorted Values
↓
Compare Adjacent Values
↓
Find Minimum Difference
This avoids checking every possible pair and gives an efficient:
Time: O(n)
Space: O(h)
solution.
Join the conversation! Your thoughts help the community grow.