LeetCode 530: Minimum Absolute Difference in BST

Problem Restatement

We are given the root of a Binary Search Tree.

We need to return the minimum absolute difference between the values of any two different nodes in the tree.

The important property is that the tree is a BST. For every node:

left subtree values < node value < right subtree values

Because of this property, an inorder traversal visits the node values in sorted order.

The problem guarantees that the tree has at least two nodes. The node values are non-negative.

Input and Output

Function shape:

def getMinimumDifference(root: Optional[TreeNode]) -> int:
    ...

Examples

Consider this BST:

    4
   / \
  2   6
 / \
1   3

The inorder traversal gives:

[1, 2, 3, 4, 6]

Now compare adjacent values:

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

The minimum difference is:

1

So the answer is:

1

Another example:

      1
       \
        48
       /  \
      12   49

The inorder traversal gives:

[1, 12, 48, 49]

Adjacent differences are:

12 - 1 = 11
48 - 12 = 36
49 - 48 = 1

The minimum difference is:

1

First Thought: Compare Every Pair

A direct solution is to collect all node values, then compare every pair.

For each pair of values a and b, compute:

abs(a - b)

Then keep the smallest value.

This works, but it ignores the BST property.

If there are n nodes, comparing every pair takes:

O(n^2)

We can do better.

Key Insight

In a sorted list, the minimum absolute difference must appear between two adjacent elements.

For example:

[1, 2, 3, 4, 6]

The closest pair cannot be 1 and 4, because values between them, such as 2 and 3, are even closer candidates.

So after sorting, we only need to compare neighbors.

A BST gives sorted values for free through inorder traversal:

left -> node -> right

Therefore, we can traverse the BST in inorder order and compare each node value with the previously visited value.

Algorithm

Use inorder traversal.

Maintain two variables:

prev
answer

prev stores the value of the previously visited node in inorder order.

answer stores the smallest difference seen so far.

During traversal:

1. Visit the left subtree.
2. Process the current node.
3. Compare node.val with prev, if prev exists.
4. Update answer.
5. Set prev = node.val.
6. Visit the right subtree.

At the end, return answer.

Correctness

Inorder traversal of a BST visits values in increasing order.

So the traversal produces the same order as sorting all node values.

In any sorted sequence, the minimum absolute difference between two values occurs between adjacent values. If two values are not adjacent, then at least one value lies between them, and one of the smaller gaps around that middle value is no larger than the larger outer gap.

The algorithm compares each value with the value immediately before it in inorder order. Therefore, it checks every adjacent pair in the sorted sequence.

Since the minimum difference must be among these adjacent pairs, the algorithm finds the correct minimum absolute difference.

Complexity

Let n be the number of nodes and h be the height of the tree.

In the worst case, a skewed tree has height n, so the space can be O(n).

For a balanced tree, the space is O(log n).

Implementation

# 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:
        prev = None
        answer = float("inf")

        def inorder(node: Optional[TreeNode]) -> None:
            nonlocal prev, answer

            if node is None:
                return

            inorder(node.left)

            if prev is not None:
                answer = min(answer, node.val - prev)

            prev = node.val

            inorder(node.right)

        inorder(root)
        return answer

Code Explanation

We initialize:

prev = None
answer = float("inf")

prev starts as None because there is no previous node before the first node in inorder traversal.

answer starts as infinity so that the first valid difference will replace it.

The traversal function is:

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

If the node is missing, we stop:

if node is None:
    return

Then we visit the left subtree:

inorder(node.left)

At this point, all smaller values have already been processed.

Now we process the current node. If there is a previous value, we compare:

answer = min(answer, node.val - prev)

We do not need abs here because inorder traversal gives increasing values, so node.val >= prev.

Then we update:

prev = node.val

Finally, we visit the right subtree:

inorder(node.right)

This continues the sorted traversal.

Iterative Version

The same idea can be implemented with an explicit stack.

from typing import Optional

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        stack = []
        node = root

        prev = None
        answer = float("inf")

        while stack or node:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()

            if prev is not None:
                answer = min(answer, node.val - prev)

            prev = node.val
            node = node.right

        return answer

This avoids recursive function calls, but the logic is the same.

Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(6),
    )
    assert s.getMinimumDifference(root) == 1

    root = TreeNode(
        1,
        None,
        TreeNode(48, TreeNode(12), TreeNode(49)),
    )
    assert s.getMinimumDifference(root) == 1

    root = TreeNode(2, TreeNode(1), None)
    assert s.getMinimumDifference(root) == 1

    root = TreeNode(10, TreeNode(5), TreeNode(20))
    assert s.getMinimumDifference(root) == 5

    print("all tests passed")

run_tests()