Minimum Absolute Difference in BST

Problem

You are given the root of a Binary Search Tree (BST). Return the minimum absolute difference between the values of any two different nodes in the tree.

Recall the BST property: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. The two nodes you compare can be anywhere in the tree — not just a parent and child.

Examples

Example 1

Input: root = [4,2,6,1,3]
Output: 1

The sorted values are [1,2,3,4,6]. The closest pair is 2 and 3 (or 3 and 4), a difference of 1.

Example 2

Input: root = [1,0,48,null,null,12,49]
Output: 1

Sorted values [0,1,12,48,49]. The closest pair is 0 and 1, difference 1.

Example 3

Input: root = [5,3,8]
Output: 2

Sorted values [3,5,8]; the smallest gap is 5 - 3 = 2.

Constraints

• The number of nodes is in the range [2, 10^4] (at least two nodes, so an answer always exists).
• 0 <= Node.val <= 10^5

Think about it first

TL;DR

In-order traversal tracks consecutive sorted values; answer is the smallest adjacent gap — O(n) time, O(h) space.

Approach 1 — Brute force: compare every pair

The naive idea ignores the BST property entirely: collect all values, then check every unordered pair and keep the smallest absolute difference.

# 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, List


def getMinimumDifference(root: Optional[TreeNode]) -> int:
    vals: List[int] = []

    def collect(node: Optional[TreeNode]) -> None:
        if not node:
            return
        vals.append(node.val)
        collect(node.left)
        collect(node.right)

    collect(root)
    best = float("inf")
    for i in range(len(vals)):
        for j in range(i + 1, len(vals)):
            best = min(best, abs(vals[i] - vals[j]))
    return int(best)

Complexity: O(n^2) time, O(n) space. With n up to 10^4 that is 10^8 comparisons, far more than needed, since an in-order traversal of the BST already yields the values in sorted order.

Approach 2 — Sort the values, then scan adjacent pairs

The closest pair in any set of numbers is always adjacent once the numbers are sorted, so you only need n - 1 comparisons, not n^2 / 2. Collect the values and sort them.

# 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, List


def getMinimumDifference(root: Optional[TreeNode]) -> int:
    vals: List[int] = []

    def collect(node: Optional[TreeNode]) -> None:
        if not node:
            return
        collect(node.left)
        vals.append(node.val)
        collect(node.right)

    collect(root)
    best = float("inf")
    for i in range(1, len(vals)):
        best = min(best, vals[i] - vals[i - 1])
    return int(best)

Note the traversal above is already in-order (left, node, right), so vals comes out sorted and no explicit sort() call is needed for a BST. If you had collected in any order, an vals.sort() would cost O(n log n).

Complexity: O(n) time for a BST via in-order (or O(n log n) if you sort a general list), O(n) space for the stored values.

Approach 3 — In-order with a running prev (no list)

In-order traversal of a BST visits values in ascending order, and the minimum gap is between consecutive visits. You never need to store all values: remember the previously visited value and compare on the fly. In-order traversal means recurse left, process the node, recurse right.

For Example 1 (root = [4,2,6,1,3]), the tree looks like this, and in-order visits its values as 1, 2, 3, 4, 6:

graph TD
    N4((4)) --> N2((2))
    N4 --> N6((6))
    N2 --> N1((1))
    N2 --> N3((3))

# 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


def getMinimumDifference(root: Optional[TreeNode]) -> int:
    prev: Optional[int] = None
    best = float("inf")

    def inorder(node: Optional[TreeNode]) -> None:
        nonlocal prev, best
        if not node:
            return
        inorder(node.left)
        if prev is not None:
            best = min(best, node.val - prev)
        prev = node.val
        inorder(node.right)

    inorder(root)
    return int(best)

Walkthrough on Example 1:

1. In-order visits 1: prev is None, so just set prev = 1.
2. Visit 2: best = min(inf, 2 - 1) = 1; prev = 2.
3. Visit 3: best = min(1, 3 - 2) = 1; prev = 3.
4. Visit 4: best = min(1, 4 - 3) = 1; prev = 4.
5. Visit 6: best = min(1, 6 - 4) = 1; prev = 6.
6. Answer: 1.

Complexity: O(n) time, O(h) space for the recursion stack (h = tree height; O(n) for a degenerate tree, O(log n) balanced). This uses only constant extra space beyond the recursion stack.

Common pitfalls

• Comparing abs() with the wrong neighbours: in an in-order walk the sequence is already ascending, so node.val - prev is non-negative; abs is harmless but unnecessary. If you compare non-adjacent values you can miss the true minimum.
• The first node: guard the very first visit (prev is None) so you do not compare against a sentinel like 0, which would corrupt the answer when all values are large.
• Assuming distinct values: the problem uses a BST where duplicates are not present, but if two values were equal the minimum difference would be 0 — the adjacent-pair scan still finds it.
• Using float('inf') and returning it: if the tree somehow had one node you would return infinity; the constraints guarantee at least two nodes, but cast to int for a clean return type.

Pattern takeaway

For any question about closeness of values in a BST — minimum difference, kth smallest, validating order — reach for in-order traversal, which streams the values in sorted order. Carrying a single prev variable lets you answer “compare each element to its neighbour” questions in one pass with no auxiliary array.