Minimum Absolute Difference in BST

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:

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:

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:

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:

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.