LeetCode 530 - Minimum Absolute Difference in BST

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem gives us the root node of a Binary Search Tree, abbreviated as BST, and asks us to find the minimum absolute difference between the values of any two distinct nodes in the tree.

A Binary Search Tree has a very important property:

Every value in the left subtree is smaller than the current node
Every value in the right subtree is larger than the current node

The input is a tree structure, not an array. Each node contains an integer value and pointers to its left and right children.

The output should be a single integer representing the smallest absolute difference between any pair of node values in the tree.

For example, in the tree:

the node values are {1, 2, 3, 4, 6}. The smallest difference between any two values is 1, because:

2 - 1 = 1
3 - 2 = 1
4 - 3 = 1

The constraints are important:

The tree contains between 2 and 10^4 nodes
Node values are between 0 and 10^5

Since the tree can contain up to ten thousand nodes, an inefficient pairwise comparison solution could become too slow. We need something better than checking every possible pair of nodes.

There are also several important edge cases:

The minimum difference may occur between parent and child nodes
The minimum difference may occur between nodes in different subtrees
The BST may be highly unbalanced, essentially behaving like a linked list
Values can be very close together, such as consecutive integers
The smallest tree size is only two nodes

The problem guarantees that there are at least two nodes, so a valid minimum difference always exists.

Approaches

Brute Force Approach

A straightforward solution is:

Traverse the entire tree and collect all node values into an array
Compare every pair of values
Compute the absolute difference for each pair
Return the smallest difference found

This works because it explicitly examines every possible pair of nodes, guaranteeing that the minimum difference will be discovered.

However, if the tree contains n nodes, there are approximately n² pairs to compare. With up to 10^4 nodes, this becomes too expensive.

The brute force approach ignores the BST structure completely, which wastes useful ordering information.

Key Insight for the Optimal Solution

The key observation is that an inorder traversal of a BST produces values in sorted order.

For example, this BST:

visited inorder gives:

1, 2, 3, 4, 6

Once the values are sorted, the minimum absolute difference must occur between two adjacent values.

Why?

Suppose we have sorted values:

a < b < c

Then:

c - a > b - a

and

c - a > c - b

So non-adjacent values can never produce the minimum difference.

This means we only need to compare each value with the previous value during inorder traversal.

That reduces the problem to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Collect all values and compare every pair
Optimal	O(n)	O(h)	Inorder traversal of BST, compare adjacent values

Here, h is the height of the tree.

Algorithm Walkthrough

Optimal Algorithm Using Inorder Traversal

Initialize a variable previous_value to track the previously visited node during inorder traversal.

Since inorder traversal visits nodes in sorted order, the previous node is always the closest smaller value. 2. Initialize a variable minimum_difference to positive infinity.

This variable stores the best answer found so far. 3. Perform an inorder traversal of the BST.

Inorder traversal follows this order:

Traverse left subtree
Visit current node
Traverse right subtree

When visiting a node, compare its value with previous_value.

Since values are visited in ascending order, the difference:

current_value - previous_value

is the smallest possible difference involving the current node and any earlier node. 5. Update minimum_difference if the current difference is smaller. 6. Update previous_value to the current node's value.

This prepares for the next inorder visit. 7. Continue traversal until all nodes have been processed. 8. Return minimum_difference.

Why it works

The correctness depends on the BST inorder property.

An inorder traversal of a BST produces values in strictly increasing sorted order. In a sorted sequence, the minimum difference between any two numbers must occur between adjacent elements.

Therefore, by comparing each node only with the previously visited node during inorder traversal, we examine all candidate minimum differences without needing to compare every pair.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.previous_value = None
        self.minimum_difference = float("inf")

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return

            inorder(node.left)

            if self.previous_value is not None:
                difference = node.val - self.previous_value
                self.minimum_difference = min(
                    self.minimum_difference,
                    difference
                )

            self.previous_value = node.val

            inorder(node.right)

        inorder(root)

        return self.minimum_difference

The implementation uses recursive inorder traversal to process the BST in sorted order.

The variable self.previous_value stores the previously visited node value. Initially it is None because no nodes have been visited yet.

The variable self.minimum_difference stores the smallest difference encountered so far. It starts as infinity so that the first valid difference will always replace it.

Inside the inorder function:

The left subtree is processed first
The current node is visited
The right subtree is processed last

When visiting the current node, the code compares its value with self.previous_value. Because inorder traversal produces sorted values, this comparison checks adjacent elements in sorted order.

After computing the difference, the current node becomes the new previous node.

The traversal eventually visits every node exactly once and returns the minimum difference found.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
    minDiff := int(^uint(0) >> 1)

    var prev *TreeNode

    var inorder func(node *TreeNode)

    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)

        if prev != nil {
            diff := node.Val - prev.Val

            if diff < minDiff {
                minDiff = diff
            }
        }

        prev = node

        inorder(node.Right)
    }

    inorder(root)

    return minDiff
}

The Go solution follows the same logic as the Python version.

A pointer prev tracks the previously visited node during inorder traversal. Since Go does not support None, we use nil to represent the absence of a previous node.

The expression:

int(^uint(0) >> 1)

creates the maximum possible integer value, which serves as the initial minimum difference.

The recursive closure inorder performs the traversal and updates minDiff as nodes are visited.

Worked Examples

Example 1

Input: [4,2,6,1,3]

Tree:

Inorder Traversal Order

1, 2, 3, 4, 6

Step-by-Step Trace

Current Node	Previous Value	Difference	Minimum Difference
1	None	None	inf
2	1	1	1
3	2	1	1
4	3	1	1
6	4	2	1

Final answer:

Example 2

Input: [1,0,48,null,null,12,49]

Tree:

Inorder Traversal Order

0, 1, 12, 48, 49

Step-by-Step Trace

Current Node	Previous Value	Difference	Minimum Difference
0	None	None	inf
1	0	1	1
12	1	11	1
48	12	36	1
49	48	1	1

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack uses tree height space

The traversal processes each node one time, so the runtime is linear in the number of nodes.

The extra space comes from recursion. In a balanced BST, the height is O(log n). In the worst case, when the tree is completely skewed, the height becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def getMinimumDifference(self, root):
        self.previous_value = None
        self.minimum_difference = float("inf")

        def inorder(node):
            if not node:
                return

            inorder(node.left)

            if self.previous_value is not None:
                difference = node.val - self.previous_value
                self.minimum_difference = min(
                    self.minimum_difference,
                    difference
                )

            self.previous_value = node.val

            inorder(node.right)

        inorder(root)

        return self.minimum_difference

solution = Solution()

# Example 1
root1 = TreeNode(
    4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(6)
)
assert solution.getMinimumDifference(root1) == 1  # consecutive values

# Example 2
solution = Solution()
root2 = TreeNode(
    1,
    TreeNode(0),
    TreeNode(48, TreeNode(12), TreeNode(49))
)
assert solution.getMinimumDifference(root2) == 1  # minimum in right subtree

# Smallest valid tree
solution = Solution()
root3 = TreeNode(1, None, TreeNode(3))
assert solution.getMinimumDifference(root3) == 2  # only one pair exists

# Left-skewed tree
solution = Solution()
root4 = TreeNode(
    5,
    TreeNode(
        4,
        TreeNode(
            3,
            TreeNode(2)
        )
    )
)
assert solution.getMinimumDifference(root4) == 1  # skewed BST

# Right-skewed tree
solution = Solution()
root5 = TreeNode(
    1,
    None,
    TreeNode(
        3,
        None,
        TreeNode(
            6,
            None,
            TreeNode(10)
        )
    )
)
assert solution.getMinimumDifference(root5) == 2  # uneven spacing

# Large value gaps
solution = Solution()
root6 = TreeNode(
    100,
    TreeNode(0),
    TreeNode(1000)
)
assert solution.getMinimumDifference(root6) == 100  # large differences

# Minimum difference deep in subtree
solution = Solution()
root7 = TreeNode(
    50,
    TreeNode(
        30,
        TreeNode(20),
        TreeNode(31)
    ),
    TreeNode(100)
)
assert solution.getMinimumDifference(root7) == 1  # subtree adjacent values

print("All tests passed.")

Test Summary

Test	Why
`[4,2,6,1,3]`	Standard balanced BST
`[1,0,48,null,null,12,49]`	Minimum difference in right subtree
Two-node tree	Smallest valid input
Left-skewed tree	Tests worst-case recursion shape
Right-skewed tree	Another worst-case tree structure
Large value gaps	Ensures subtraction logic works correctly
Deep subtree minimum	Confirms traversal handles nested nodes correctly

Edge Cases

Two-Node Tree

The smallest valid input contains exactly two nodes. This case is important because there is only one possible pair of values.

A buggy implementation might assume multiple comparisons occur during traversal. Our implementation handles this correctly because the first valid comparison immediately updates minimum_difference.

Highly Skewed Tree

A BST can become completely unbalanced, behaving like a linked list:

This tests whether recursion and traversal logic still work correctly when the height becomes O(n).

The implementation still processes nodes in sorted order and correctly computes adjacent differences.

Minimum Difference Deep in a Subtree

The closest pair of values may not involve the root at all.

Example:

The minimum difference is between 30 and 31, both inside the left subtree.

A naive implementation that only compares parent-child relationships could miss this case. Inorder traversal avoids this issue because it compares all adjacent sorted values globally across the entire tree.