Minimum Absolute Difference in BST: Inorder Traversal for Sorted Order

You are given the root of a binary search tree. Return the minimum absolute difference between the values of any two different nodes in the tree.

This is LeetCode 530: Minimum Absolute Difference in BST. It is an easy-level tree problem, but the clean solution depends on recognizing a fundamental property of binary search trees. If you try to compare every pair of nodes, you will end up with an O(n^2) approach. The trick is to leverage what makes a BST special.

The problem

Given a BST, find the two nodes whose values are closest together and return the absolute difference between them. For example, given the tree [4, 2, 6, 1, 3], the minimum absolute difference is 1 (which occurs between the pairs 1-2, 2-3, and 3-4).

The key insight

In a binary search tree, an inorder traversal visits nodes in sorted (ascending) order. If you line up all the values in sorted order, the minimum absolute difference must occur between two consecutive values. You never need to compare non-adjacent values, because if a < b < c, then b - a and c - b are both smaller than c - a.

This means you can solve the problem with a single inorder traversal. As you visit each node, compare it to the previously visited node. Track the smallest gap you have seen so far.

The solution

def get_minimum_difference(root):
    prev = [None]
    min_diff = [float('inf')]

    def inorder(node):
        if node is None:
            return
        inorder(node.left)
        if prev[0] is not None:
            min_diff[0] = min(min_diff[0], node.val - prev[0])
        prev[0] = node.val
        inorder(node.right)

    inorder(root)
    return min_diff[0]

Step-by-step walkthrough

Let's trace through the BST [4, 2, 6, 1, 3] step by step. At each node, we compare the current value to the previous inorder value and update the minimum difference.

Notice how we only ever compare consecutive inorder values. We never need to look at all possible pairs, because the BST property guarantees that the closest values are always neighbors in the sorted order.

Complexity analysis

Time: O(n), where n is the number of nodes. We visit every node exactly once during the inorder traversal.

Space: O(h), where h is the height of the tree. The recursion stack grows as deep as the tree. For a balanced BST, h = log n. For a completely skewed tree, h = n.

The building blocks

1. Inorder traversal of a BST

The core technique here is inorder traversal, which visits nodes in left-root-right order. For a BST, this produces values in ascending sorted order.

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

This pattern is the foundation for many BST problems. Once you have the values in sorted order, problems like finding the minimum gap, validating the BST, or finding the kth smallest element all become simple linear scans.

2. Tracking the previous value during traversal

Instead of collecting all values into an array and then scanning for the minimum gap, you can do it in a single pass by keeping track of the previously visited value.

prev = [None]
min_diff = [float('inf')]

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    if prev[0] is not None:
        min_diff[0] = min(min_diff[0], node.val - prev[0])
    prev[0] = node.val
    inorder(node.right)

We use prev = [None] (a list) instead of a plain variable because Python's nested functions can read but not reassign variables from the enclosing scope without the nonlocal keyword. Wrapping it in a list and mutating prev[0] is a common workaround. You could also use nonlocal prev if you prefer.

Edge cases

• Two nodes only: the tree has exactly two nodes, so the answer is simply the absolute difference between them.
• All nodes in a line (skewed tree): the inorder traversal still works correctly, but the recursion stack goes O(n) deep.
• Duplicate-adjacent values: the problem states all values are unique in a BST, so you will not encounter node.val == prev. The minimum difference is always at least 1.
• Large value gaps: the algorithm handles this naturally. If consecutive inorder values are far apart, min_diff simply does not update.

From understanding to recall

You just traced through an inorder traversal on a BST and watched the minimum gap shrink as you compared consecutive values. The connection between "BST" and "sorted inorder" probably feels obvious right now. But in a week, when you see a different BST problem, will you immediately reach for inorder traversal? Or will you waste time thinking about brute-force pair comparisons?

Understanding is not the same as recall. Spaced repetition bridges the gap. By practicing this pattern at increasing intervals, you train yourself to recognize "BST problem = think inorder" automatically. After a few reps, the inorder traversal skeleton becomes second nature, and problems like this one take minutes instead of thirty.

Related posts

• Validate Binary Search Tree - Uses the same inorder BST property to check if all values appear in strictly increasing order
• Kth Smallest Element in a BST - Another inorder traversal problem where you stop after visiting the kth node
• Binary Search Tree Iterator - Implements an iterator that returns BST values in sorted order using an explicit stack