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


class Solution:
    def getMinimumDifference(self, 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 — slow and wasteful, since the BST hands us sorted order almost for free.

Approach 2 — Sort the values, then scan adjacent pairs

The insight: 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


class Solution:
    def getMinimumDifference(self, 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)

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

# 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.prev: Optional[int] = None
        self.best = float("inf")

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

        inorder(root)
        return int(self.best)

Walkthrough on Example 1 (root = [4,2,6,1,3]):

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 is the tightest solution — constant extra space beyond the 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.