Minimum Absolute Difference in BST

Difficulty: Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree
Link: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

Problem Description

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.

Example 1:


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

Example 2:


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

Constraints:

The number of nodes in the tree is in the range [2, 104].
0 <= Node.val <= 105

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Solution

1. Problem Deconstruction

Technical Restatement
Given the root node of a Binary Search Tree (BST), determine the smallest possible absolute difference between the values of any two distinct nodes in the tree. A BST is defined such that for any node, all values in its left subtree are strictly less than its value, and all values in its right subtree are strictly greater than its value.

Beginner-Friendly Restatement
Imagine you have a special family tree where each person has a number, and the tree is arranged so that all left-side descendants have smaller numbers while right-side descendants have larger numbers. Your task is to find the two closest numbers in this entire family tree and report how close they are.

Mathematical Formulation
Let $V$ be the set of all node values in the BST:
$V = \{v \mid v \text{ is the value of some node in the tree}\}$
The problem seeks:
$\min\{|v_i - v_j| \mid v_i, v_j \in V, v_i \neq v_j\}$
For a BST, this is equivalent to:
$\min\{v_{k+1} - v_k \mid \text{where } v_1, v_2, ..., v_n \text{ are the sorted node values}\}$

Constraint Analysis

Number of nodes in [2, 10⁴]:
- Limits solutions to at most O(n log n) time complexity
- O(n²) approaches would require ~10⁸ operations (borderline acceptable but suboptimal)
- Implies the tree could be highly unbalanced (effectively a linked list)
Node values in [0, 10⁵]:
- Values are non-negative, simplifying absolute difference calculations
- Maximum possible difference is bounded by 10⁵
- No overflow concerns for standard integer arithmetic
Hidden edge cases:
- Two-node trees (minimum possible case)
- Perfectly balanced vs completely unbalanced trees
- Duplicate values are impossible in a proper BST
- Very large differences between consecutive values in sorted order

2. Intuition Scaffolding

Real-World Metaphor
Imagine a library with books organized by Dewey Decimal System. You’re looking for two books with the most similar classification numbers. Since the books are already sorted on shelves, you only need to check adjacent books rather than comparing every possible pair.

Gaming Analogy
In a skill-based matchmaking system, players are ranked by skill level (BST structure). Finding the closest-ranked opponents means checking players who would be adjacent in the global leaderboard, not comparing all possible player pairs.

Math Analogy
Given a sorted sequence $a_1, a_2, ..., a_n$ , the minimum difference between any two elements must occur between some consecutive pair $a_i$ and $a_{i+1}$ in the sorted sequence. For a BST, an in-order traversal naturally produces this sorted sequence.

Common Pitfalls

Global min/max approach: Thinking the minimum difference must involve the smallest or largest values
Level-order traversal: Attempting BFS which doesn’t preserve value ordering
Only checking parent-child pairs: The closest values might be in different subtrees
Forgetting BST properties: Attempting to sort all values manually instead of using in-order traversal
Handling duplicates: In a proper BST, duplicates shouldn’t exist, but the logic should be clear

3. Approach Encyclopedia

Approach 1: Brute Force (Collect & Compare)

1. Traverse tree, collect all values into array
2. Sort the array (redundant for BST but general approach)
3. Compare every consecutive pair in sorted array
4. Track minimum difference

Time Complexity: O(n log n) for sort + O(n) traversal = O(n log n)
Space Complexity: O(n) for value storage
Visualization:

    4
   / \
  2   6
 / \
1   3

Values: [4,2,6,1,3] → Sorted: [1,2,3,4,6]
Diffs:  [1,1,1,2] → Min: 1

Approach 2: In-Order Traversal (Optimal)

1. Initialize prev = None, min_diff = ∞
2. Perform in-order traversal:
   - Traverse left subtree
   - If prev exists, update min_diff with (current.val - prev)
   - Set prev = current.val
   - Traverse right subtree
3. Return min_diff

Time Complexity: O(n) - single tree traversal
Space Complexity: O(h) - recursion stack height, O(n) worst-case for unbalanced tree
Complexity Proof:
Each node visited exactly once: T(n) = T(k) + T(n-k-1) + O(1)
For balanced tree: T(n) = 2T(n/2) + O(1) → O(n) by Master Theorem
For unbalanced tree: T(n) = T(n-1) + O(1) → O(n)

Visualization:

In-order: 1 → 2 → 3 → 4 → 6
Diffs:    (1)  (1)  (1)  (2)
Min: 1

Approach 3: Iterative In-Order

1. Initialize stack, prev = None, min_diff = ∞
2. While current exists or stack not empty:
   - Push all left children to stack
   - Pop node, compare with prev, update min_diff
   - Set prev = current value
   - Move to right child

Time/Space: Same as recursive approach

4. Code Deep Dive

def getMinimumDifference(root: TreeNode) -> int:
    prev = None
    min_diff = float('inf')
    
    def in_order_traversal(node):
        nonlocal prev, min_diff
        
        if not node:
            return
        
        # Traverse left subtree
        in_order_traversal(node.left)
        
        # Process current node
        if prev is not None:
            min_diff = min(min_diff, node.val - prev)
        prev = node.val
        
        # Traverse right subtree  
        in_order_traversal(node.right)
    
    in_order_traversal(root)
    return min_diff

Line-by-Line Analysis

prev = None: Tracks the previous node’s value during in-order traversal
min_diff = float('inf'): Initializes to largest possible difference
if not node: return: Base case for recursion termination
in_order_traversal(node.left): Processes all smaller values first
if prev is not None: Skip comparison for first node in traversal
node.val - prev: Since in-order produces sorted sequence, difference is always positive
prev = node.val: Updates previous before moving to larger values

Edge Case Handling

Example 1: [4,2,6,1,3]
In-order: 1→2→3→4→6
Differences: 1,1,1,2 → Correctly returns 1
Example 2: [1,0,48,null,null,12,49]
In-order: 0→1→12→48→49
Differences: 1,11,36,1 → Min is 1 (between 0-1 and 48-49)
Two-node tree: [1,3]
Direct comparison yields difference of 2

5. Complexity War Room

Hardware-Aware Analysis
At maximum constraint (n=10⁴):

Recursion depth: Up to 10⁴ stack frames × ~100 bytes/frame ≈ 1MB (fits in L1/L2 cache)
Value storage: 10⁴ integers × 4 bytes = 40KB (fits in CPU cache)
Memory access pattern: Sequential during in-order traversal (cache-friendly)

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n log n)	O(n)	9/10	✅ Acceptable
Recursive In-Order	O(n)	O(h)	8/10	✅ Preferred
Iterative In-Order	O(n)	O(h)	7/10	✅ Good Alternative
Morris Traversal	O(n)	O(1)	5/10	⚠️ Advanced

6. Pro Mode Extras

Variants & Extensions

Multiple Transactions: “Find k pairs with smallest absolute differences”
Non-BST Version: “Find minimum difference in any binary tree” → O(n log n) sort required
Streaming Version: “Process nodes as they arrive” → maintain sorted structure
Range Queries: “Find minimum difference in subtree” → segment tree approach

Interview Cheat Sheet

First Mention: “BST property enables O(n) solution via in-order traversal”
Key Insight: “Minimum difference must occur between consecutive elements in sorted order”
Space Optimization: “Iterative approach avoids recursion stack overflow for large n”
Testing Strategy: “Verify with completely unbalanced trees and two-node cases”

Advanced Optimization: Morris Traversal

def getMinimumDifference(root):
    curr, prev = root, None
    min_diff = float('inf')
    
    while curr:
        if not curr.left:
            # Process current
            if prev: min_diff = min(min_diff, curr.val - prev.val)
            prev, curr = curr, curr.right
        else:
            # Find inorder predecessor
            pred = curr.left
            while pred.right and pred.right != curr:
                pred = pred.right
            
            if not pred.right:
                pred.right = curr  # Create thread
                curr = curr.left
            else:
                pred.right = None  # Remove thread
                if prev: min_diff = min(min_diff, curr.val - prev.val)
                prev, curr = curr, curr.right
                
    return min_diff

O(1) space complexity by reusing null pointers

#530 - Minimum Absolute Difference in BST