Minimum Distance Between BST Nodes

This approach involves iterating through all possible pairs of nodes in the tree, calculating the absolute difference of their values, and keeping track of the minimum difference found. It does not utilize the properties of a Binary Search Tree.

• Create an empty list values.
• Define a helper function collectValues that performs a pre-order traversal of the tree and adds each node's value to the values list.
• Call collectValues starting from the root.
• Initialize minDifference to Integer.MAX_VALUE.
• Use a nested loop to iterate through all pairs of elements in the values list.
• For each pair, calculate the absolute difference and update minDifference if the new difference is smaller.
• Return minDifference.

First, we traverse the entire tree to collect all node values into a list. Any traversal method (pre-order, in-order, post-order) works for this step. After populating the list, we use two nested loops to consider every unique pair of values (values[i], values[j]). For each pair, we calculate the absolute difference abs(values[i] - values[j]). We maintain a variable, minDifference, initialized to a very large value. This variable is updated whenever a smaller difference is found. After checking all pairs, minDifference will hold the minimum difference between any two nodes.

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

class Solution {
    public int minDiffInBST(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        collectValues(root, values);
        
        int minDifference = Integer.MAX_VALUE;
        for (int i = 0; i < values.size(); i++) {
            for (int j = i + 1; j < values.size(); j++) {
                minDifference = Math.min(minDifference, Math.abs(values.get(i) - values.get(j)));
            }
        }
        return minDifference;
    }

    private void collectValues(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        values.add(node.val);
        collectValues(node.left, values);
        collectValues(node.right, values);
    }
}