🎨 Try our Free AI Image Generation Feature

530. Minimum Absolute Difference in BST

avatar
Dare2Solve

11 months ago

530. Minimum Absolute Difference in BST

Description

The problem involves finding the minimum absolute difference between values of any two nodes in a Binary Search Tree (BST). Given the properties of a BST, we can leverage an in-order traversal to retrieve node values in a sorted order.

Intuition

The key intuition behind solving this problem is that an in-order traversal of a BST yields node values in ascending order. Thus, the minimum difference will always be found between two consecutive values in this sorted order.

Approach

  1. In-Order Traversal: - Perform an in-order traversal of the BST to collect the node values in a list. This ensures the values are in ascending order.
  2. Compute Minimum Difference: - Iterate through the sorted list of values and compute the differences between consecutive elements. - Track the minimum difference encountered during this iteration.
  3. Edge Cases: - Handle the case where the tree is empty. - Ensure the solution works for trees with only one node or two nodes.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the BST. This is because we perform an in-order traversal of all nodes and then a single pass to compute the minimum difference.

Space Complexity:

O(n) for storing the values of the nodes in a list during the in-order traversal.

Code

C++

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector vals;
        inOrder(root, vals);

        int minDiff = INT_MAX;
        for (int i = 1; i < vals.size(); ++i) {
            minDiff = min(minDiff, vals[i] - vals[i - 1]);
        }
        return minDiff;
    }
private:
    void inOrder(TreeNode* node, vector& vals) {
        if (!node) return;
        inOrder(node->left, vals);
        vals.push_back(node->val);
        inOrder(node->right, vals);
    }
};

Python

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def inOrder(node: Optional[TreeNode], values: List[int]):
            if node is None:
                return
            inOrder(node.left, values)
            values.append(node.val)
            inOrder(node.right, values)
        
        values = []
        inOrder(root, values)
        
        min_diff = float('inf')
        for i in range(1, len(values)):
            min_diff = min(min_diff, values[i] - values[i - 1])
        
        return min_diff

Java

class Solution {
    public int getMinimumDifference(TreeNode root) {
        List values = new ArrayList<>();
        inOrder(root, values);
        
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < values.size(); i++) {
            minDiff = Math.min(minDiff, values.get(i) - values.get(i - 1));
        }
        return minDiff;
    }
    private void inOrder(TreeNode node, List values) {
        if (node == null) return;
        inOrder(node.left, values);
        values.add(node.val);
        inOrder(node.right, values);
    }
}

JavaScript

var getMinimumDifference = function (root) {
    let min = Number.MAX_VALUE;
    if (root === null)
        return 0;
    let arr = [];
    let inOrder = function (root) {
        root.left && inOrder(root.left);
        arr.push(root.val)
        root.right && inOrder(root.right);
    }
    inOrder(root);
    let i = 0;
    let j = i + 1;
    while (j < arr.length) {
        console.log((arr[j] - arr[i]))
        min = Math.min(min, (arr[j] - arr[i]))
        i++;
        j++;
    }
    return min;
};