Minimum Absolute Difference in BST

A more optimized approach is to collect all node values, sort them, and then find the minimum difference between adjacent elements. The minimum difference in a sorted set of numbers will always occur between two consecutive numbers.

• Create an empty list values.
• Traverse the tree (e.g., using pre-order traversal) and add all node values to the values list.
• Sort the values list using Collections.sort().
• Initialize minDiff to Integer.MAX_VALUE.
• Iterate through the sorted list from the second element (i = 1 to values.size() - 1).
• In each iteration, calculate the difference: diff = values.get(i) - values.get(i - 1).
• Update minDiff = Math.min(minDiff, diff).
• Return minDiff.

Similar to the brute-force approach, we first traverse the tree to collect all node values into a list. Any traversal order (pre-order, in-order, or post-order) works for this step. Once we have the list of all values, we sort it in ascending order. After sorting, the problem is reduced to finding the minimum difference between any two adjacent elements in the sorted list. We iterate through the sorted list from the second element and calculate the difference between the current element and the previous one. We keep track of the minimum difference found during this single pass.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int getMinimumDifference(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        collectValues(root, values);
        
        Collections.sort(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 collectValues(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        values.add(node.val);
        collectValues(node.left, values);
        collectValues(node.right, values);
    }
}