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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Absolute Difference in BST

Difficulty: Easy

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.

Key Insights

  • The values in a Binary Search Tree are ordered, which means an in-order traversal will yield sorted values.
  • The minimum absolute difference in values will be between consecutive nodes in the sorted order.
  • We can perform an in-order traversal to collect the values and then calculate the differences between consecutive values.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the tree, since we visit each node once during the in-order traversal. Space Complexity: O(N) - for storing the values of the nodes during the traversal.

Solution

The solution involves performing an in-order traversal of the BST to retrieve the node values in sorted order. By comparing the differences between consecutive values, we can determine the minimum absolute difference.

The algorithm can be summarized as follows:

  1. Initialize an empty list to store the values of the nodes.
  2. Perform an in-order traversal of the BST, appending each node's value to the list.
  3. Iterate through the list of values and compute the absolute differences between consecutive elements, keeping track of the minimum difference found.

Code Solutions

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

def getMinimumDifference(root: TreeNode) -> int:
    values = []
    
    # In-order traversal to get the values in sorted order
    def in_order(node):
        if not node:
            return
        in_order(node.left)
        values.append(node.val)
        in_order(node.right)
        
    in_order(root)
    
    # Calculate the minimum absolute difference
    min_diff = float('inf')
    for i in range(1, len(values)):
        min_diff = min(min_diff, values[i] - values[i - 1])
    
    return min_diff
← Back to All Questions