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

Code

        50
       /  \
     30    70
    /     /  \
   20    60   80

The inorder traversal is:

Code

20 → 30 → 50 → 60 → 70 → 80

The differences between adjacent values are:

Code

30 - 20 = 10
50 - 30 = 20
60 - 50 = 10
70 - 60 = 10
80 - 70 = 10

Therefore, the minimum absolute difference is:

Code

Key Concept

The most important property of a Binary Search Tree is:

Code

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:

Code

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:

Code

10, 20, 25, 40

The possible differences include:

Code

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:

Code

current value - previous value

Update minDiff.

Store the current node's value in prev.
Traverse the right subtree.
Return minDiff.

Java Code

Java

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

Java

int prev = -1;
int minDiff = Integer.MAX_VALUE;

`prev`

prev stores the value of the previous node visited during inorder traversal.

Initially:

Code

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:

Java

Integer.MAX_VALUE

This allows the first calculated difference to replace it.

2. Main Function

Java

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

Java

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

Java

inorder(root.left);

We first visit the left subtree.

This is important because inorder traversal follows:

Code

Left → Root → Right

For a BST, this produces values in sorted order.

5. Calculate Difference

Java

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:

Code

current value - previous value

For example:

Code

Previous = 30
Current  = 50

Difference = 50 - 30
           = 20

Then:

Java

Math.min(minDiff, 20)

keeps the smaller value.

6. Update Previous Value

Java

prev = root.data;

After processing the current node, its value becomes the previous value for the next node.

For example:

Code

20 → 30 → 50

When processing 30:

Code

prev = 20
current = 30
difference = 10

After processing:

Code

prev = 30

Then when processing 50:

Code

prev = 30
current = 50
difference = 20

7. Traverse Right Subtree

Java

inorder(root.right);

Finally, we visit the right subtree.

This maintains the inorder traversal:

Code

Left → Root → Right

Dry Run

Consider:

Code

        50
       /  \
     30    70
    /     /  \
   20    60   80

Inorder Traversal

The traversal produces:

Code

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:

Code

minDiff = 10

So the answer is:

Code

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:

Code

n × (n - 1) / 2

pairs.

That results in:

Code

O(n²)

time complexity.

But the BST property gives us a better solution.

Since inorder traversal already gives sorted values:

Code

10 → 15 → 30 → 45 → 50

we only need to check:

Code

Therefore, every node is processed only once.

Why root.data - prev Instead of Math.abs()?

Normally, absolute difference is:

Java

Math.abs(a - b)

But here, inorder traversal gives values in increasing order.

Therefore:

Code

current >= previous

So:

Code

current - previous

will never be negative.

For example:

Code

20 → 30 → 50 → 60

The differences are:

Code

30 - 20 = 10
50 - 30 = 20
60 - 50 = 10

Thus, Math.abs() is unnecessary.

Another Example

Consider:

Code

Inorder traversal:

Code

10 → 30 → 60 → 90

Differences:

Code

30 - 10 = 20
60 - 30 = 30
90 - 60 = 30

Therefore:

Code

Answer = 20

Complexity Analysis

Time Complexity

Code

O(n)

Each node is visited exactly once during inorder traversal.

Auxiliary Space

Code

O(h)

where h is the height of the BST.

The space is used by the recursion stack.

For a balanced BST:

Code

h = O(log n)

For a skewed BST:

Code

h = O(n)

Therefore, the expected auxiliary space is:

Code

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:

Code

BST
 ↓
Inorder Traversal
 ↓
Sorted Values
 ↓
Compare Adjacent Values
 ↓
Find Minimum Difference

This avoids checking every possible pair and gives an efficient:

Code

Time: O(n)
Space: O(h)

solution.