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;
};