LeetCode 530: Minimum Absolute Difference in BST Solution in Python – A Step-by-Step Guide

What Is LeetCode 530: Minimum Absolute Difference in BST?

In LeetCode 530: Minimum Absolute Difference in BST, you’re given the root of a Binary Search Tree (BST), and your task is to find the minimum absolute difference between the values of any two nodes. A BST ensures that for any node, all left subtree values are less than the node’s value, and all right subtree values are greater, making inorder traversal sorted. For example, in a BST [4, 2, 6, 1, 3], the minimum difference is 1 (between 1 and 2). This problem builds on LeetCode 94: Binary Tree Inorder Traversal.

Problem Statement

• Input: root (TreeNode)—root of a BST.
• Output: Integer—minimum absolute difference between any two node values.
• Rules: BST properties hold; at least two nodes.

Constraints

• Number of nodes: 2 to 10⁴.
• Node values: 0 to 10⁵.

Examples

• Input: root = [4,2,6,1,3]
• Output: 1
• Tree:
``` 4 / \ 2 6 / \ 1 3 ```
• Inorder: [1, 2, 3, 4, 6], min diff = 1 (2-1).
• Input: root = [1,0,48,null,null,12,49]
• Output: 1
• Inorder: [0, 1, 12, 48, 49], min diff = 1 (1-0).
• Input: root = [5,4,7]
• Output: 1
• Inorder: [4, 5, 7], min diff = 1 (5-4).

Understanding the Problem: Finding the Smallest Gap

To solve LeetCode 530: Minimum Absolute Difference in BST in Python, we need to find the smallest absolute difference between any two node values in a BST. Since BST inorder traversal yields a sorted sequence, the minimum difference must be between adjacent values in that order. A naive approach might collect all values and compare every pair, but with up to 10⁴ nodes, we can optimize using inorder properties. We’ll explore:

• Best Solution (Inorder Traversal with Previous Tracking): O(n) time, O(h) space (h = tree height)—efficient and sleek.
• Alternative Solution (Inorder to Array with Pairwise Comparison): O(n) time, O(n) space—simple but uses more memory.

Let’s dive into the inorder solution with a friendly breakdown!

Best Solution: Inorder Traversal with Previous Tracking

Why Inorder with Previous Tracking Wins

The inorder traversal with previous tracking is the best for LeetCode 530 because it leverages the BST’s sorted property to compute differences on-the-fly in O(n) time, using O(h) space (recursion stack), avoiding the need to store all values. It’s like walking through the tree and measuring gaps as you go!

How It Works

Think of this as a tree-walking tape measure:

• Step 1: Inorder Traversal:
• Visit left subtree, node, right subtree—gives sorted order.
• Step 2: Track Previous Value:
• Keep the last visited node’s value (prev).
• Compare with current node to find difference.
• Step 3: Update Minimum:
• Track smallest difference seen (min_diff).
• Why It Works:
• BST inorder is sorted, so min diff is between adjacent values.
• One pass computes all differences.

It’s like a BST gap finder!

Step-by-Step Example

Example: root = [4,2,6,1,3]

• Init: prev = None, min_diff = float('inf').
• Inorder:
• Left to (2):
• Left to (1):
• Visit 1, prev = None, set prev = 1.
• Visit 2, prev = 1, diff = 2-1 = 1, min_diff = 1, prev = 2.
• Right to (3):
• Visit 3, prev = 2, diff = 3-2 = 1, min_diff = 1, prev = 3.
• Visit 4, prev = 3, diff = 4-3 = 1, min_diff = 1, prev = 4.
• Right to (6):
• Visit 6, prev = 4, diff = 6-4 = 2, min_diff = 1, prev = 6.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        # Step 1: Initialize variables
        self.prev = None
        self.min_diff = float('inf')

        # Step 2: Inorder traversal helper
        def inorder(node):
            if not node:
                return

            # Traverse left
            inorder(node.left)

            # Process current node
            if self.prev is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev)
            self.prev = node.val

            # Traverse right
            inorder(node.right)

        # Step 3: Start traversal
        inorder(root)
        return self.min_diff

• Lines 10-11: Instance variables for previous value and min difference.
• Lines 14-15: Base case: skip null nodes.
• Line 18: Recurse left (inorder).
• Lines 21-23: If prev set, compute diff with current, update prev.
• Line 26: Recurse right.
• Line 29: Start traversal.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h ≤ n).

It’s like a BST difference tracker!

Alternative Solution: Inorder to Array with Pairwise Comparison

Why an Alternative Approach?

The inorder to array with pairwise comparison solution collects all BST values into a sorted array via inorder traversal, then compares adjacent pairs to find the minimum difference. It’s O(n) time and O(n) space—simple but uses extra memory. Great for array lovers!

How It Works

Picture this as a BST-to-list measurer:

• Step 1: Inorder traversal to array.
• Step 2: Compare adjacent elements in sorted list.
• Step 3: Return smallest difference.

It’s like a BST list gap checker!

Step-by-Step Example

Example: root = [5,4,7]

• Step 1: Inorder: [4, 5, 7].
• Step 2: Compare:
• 5 - 4 = 1.
• 7 - 5 = 2.
• Step 3: Min = 1.
• Result: 1.

Code for Array Approach

Copy codeclass Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        # Step 1: Inorder traversal to array
        values = []

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

        inorder(root)

        # Step 2: Find min difference in array
        min_diff = float('inf')
        for i in range(1, len(values)):
            min_diff = min(min_diff, values[i] - values[i-1])

        # Step 3: Return result
        return min_diff

• Line 4: Array to store values.
• Lines 6-11: Inorder builds sorted list.
• Lines 14-16: Compare adjacent pairs.
• Time Complexity: O(n)—traversal and scan.
• Space Complexity: O(n)—array storage.

It’s an array-based gap finder!

Comparing the Two Solutions

• Inorder with Prev (Best):
• Pros: O(n), O(h), space-efficient.
• Cons: Recursive state tracking.
• Inorder to Array (Alternative):
• Pros: O(n), O(n), simple logic.
• Cons: Extra space.

Inorder with prev wins for efficiency!

Additional Examples and Edge Cases

• ** [1,2]: 1.
• ** [5,1,10]: 4 (5-1).
• ** [1,null,3,null,5]: 2 (3-1).

Inorder with prev handles them all!

Complexity Recap

• Inorder with Prev: Time O(n), Space O(h).
• Inorder to Array: Time O(n), Space O(n).

Inorder with prev’s the space champ!

Key Takeaways

• Inorder: BST sorting—learn at Python Basics!
• Array: Simple but costly.
• Trees: Differences are fun.
• Python: Recursion or lists, your pick!

Final Thoughts: Measure That Gap!

LeetCode 530: Minimum Absolute Difference in BST in Python is a delightful tree challenge. Inorder with previous tracking is your fast track, while array comparison keeps it basic. Want more? Try LeetCode 94: Binary Tree Inorder Traversal or LeetCode 98: Validate BST. Ready to traverse? Head to Solve LeetCode 530 on LeetCode and find that smallest difference today!