We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Absolute Difference in BST

Number: 530

Difficulty: Easy

Paid? No

Companies: Meta, Amazon, Google

Problem Description

Given the root of a Binary Search Tree (BST), find and return the minimum absolute difference between the values of any two different nodes in the tree.

Key Insights

  • Inorder traversal of a BST yields the node values in sorted order.
  • The minimum absolute difference will always be between two consecutive values in this sorted order.
  • A single traversal (inorder) is sufficient to compute the answer by comparing the current node’s value with the previous node’s value.
  • Using an extra variable to store the previous node’s value avoids the need for extra space to store the sorted list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the BST. Space Complexity: O(n) in the worst-case for the call stack (tree height) for a skewed tree; O(log n) on average for a balanced tree.

Solution

The solution performs an inorder traversal of the BST to retrieve the node values in sorted order. During the traversal, it keeps track of the previously visited node’s value. At each node, the difference between the current node’s value and the previous node’s value is computed, and the minimum difference is updated accordingly. This method leverages the BST’s inherent property of ordered traversal to efficiently calculate the desired result without additional data structures.

Code Solutions

# Define the TreeNode class for clarity
class 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:
        # Initialize previous node value (None initially) and the minimum difference as infinity
        self.prev = None
        self.min_diff = float('inf')
        
        # Inorder traversal function to process nodes in sorted order
        def inorder(node):
            if not node:
                return
            # Process left subtree
            inorder(node.left)
            # If there is a previous node, update the minimum difference
            if self.prev is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev)
            # Update the previous node value to the current node's value
            self.prev = node.val
            # Process right subtree
            inorder(node.right)
            
        inorder(root)
        return self.min_diff
← Back to All Questions