Leetcode – Minimum Absolute Difference in BST Solution in Python

Introduction

The Minimum Absolute Difference in BST problem on Leetcode is a stimulating challenge that blends tree traversal techniques with some mathematical insights. It serves as a quintessential example of a problem where a good grasp of data structures and their properties leads to an efficient solution. This exhaustive article will dissect the Minimum Absolute Difference in BST problem, understand the nuances of Binary Search Trees (BST), and explore various approaches to solving it using Python.

The problem is described as follows:

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.

For Example

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

Preliminary: Understanding Binary Search Trees (BST)

Before we dive into solving the problem, it’s imperative to understand the characteristics of a Binary Search Tree (BST). A BST is a binary tree where for each node, the nodes in the left subtree have values less than or equal to the node’s value, and nodes in the right subtree have values greater than the node’s value.

This property leads to an important observation: when you perform an in-order traversal of a BST, the values of the nodes are visited in sorted (non-decreasing) order. We can use this property to solve the Minimum Absolute Difference in BST problem efficiently.

Approach 1: In-Order Traversal and Linear Scan

We can leverage the in-order traversal to solve this problem. By performing an in-order traversal of the BST, we can generate a sorted list of the values in the tree. The minimum absolute difference must occur between two adjacent elements in this sorted list since they are the closest in value.

Here is the Python code for this approach.

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

def getMinimumDifference(root):
    # Perform in-order traversal and store values in a list
    def in_order_traversal(node, vals):
        if node:
            in_order_traversal(node.left, vals)
            vals.append(node.val)
            in_order_traversal(node.right, vals)
    
    # List to store the in-order traversal values
    vals = []
    in_order_traversal(root, vals)
    
    # Calculate the minimum absolute difference between adjacent values
    return min(abs(a - b) for a, b in zip(vals, vals[1:]))

This approach has a time complexity of O(n) and space complexity of O(n) where n is the number of nodes in the tree.

Approach 2: Optimized In-Order Traversal

Although the first approach is efficient, it is not space-optimized. We can optimize the space by keeping track of the previous node and the minimum difference during the in-order traversal, rather than storing all the values.

Here is the Python code for this optimized approach.

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

def getMinimumDifference(root):
    # In-order traversal
    def in_order_traversal(node):
        nonlocal prev, min_diff
        if node:
            in_order_traversal(node.left)
            if prev is not None:
                min_diff = min(min_diff, abs(node.val - prev.val))
            prev = node
            in_order_traversal(node.right)
    
    # Variables to store previous node and minimum difference
    prev = None
    min_diff = float('inf')
    
    # Perform the in-order traversal
    in_order_traversal(root)
    
    # Return the minimum difference
    return min_diff

This approach also has a time complexity of O(n), but the space complexity is reduced to O(h), where h is the height of the tree, due to the recursive stack.

Conclusion

In this extensive article, we investigated the Minimum Absolute Difference in BST problem on Leetcode. We understood the critical properties of Binary Search Trees and explored two approaches using in-order traversal. The first approach involved storing values in a list, while the second approach optimized space by keeping track of the previous node and minimum difference during the traversal.