Minimum Distance Between BST Nodes

• 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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int minDiffInBST(TreeNode root) {6        List<Integer> values = new ArrayList<>();7        collectValues(root, values);8        9        int minDifference = Integer.MAX_VALUE;10        for (int i = 0; i < values.size(); i++) {11            for (int j = i + 1; j < values.size(); j++) {12                minDifference = Math.min(minDifference, Math.abs(values.get(i) - values.get(j)));13            }14        }15        return minDifference;16    }17 18    private void collectValues(TreeNode node, List<Integer> values) {19        if (node == null) {20            return;21        }22        values.add(node.val);23        collectValues(node.left, values);24        collectValues(node.right, values);25    }26}

• Create an empty list sortedValues.
• Implement a recursive inOrderTraversal helper function that traverses the tree in-order and appends each node's value to the sortedValues list.
• Call inOrderTraversal starting from the root.
• Initialize minDifference to Integer.MAX_VALUE.
• Iterate through the sortedValues list from the second element (i=1) to the end.
• In each step, calculate sortedValues.get(i) - sortedValues.get(i - 1) and update minDifference if this new difference is smaller.
• Return minDifference.

We first perform a standard recursive in-order traversal of the BST. During the traversal, we add each node's value to a list. Since it's an in-order traversal on a BST, the list will automatically be sorted in non-decreasing order. After the traversal is complete, we iterate through the sorted list from the second element. In each iteration, we calculate the difference between the current element and the previous element. We keep track of the minimum difference found during this iteration. The final result is the minimum difference found among all adjacent pairs.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int minDiffInBST(TreeNode root) {6        List<Integer> sortedValues = new ArrayList<>();7        inOrderTraversal(root, sortedValues);8        9        int minDifference = Integer.MAX_VALUE;10        for (int i = 1; i < sortedValues.size(); i++) {11            minDifference = Math.min(minDifference, sortedValues.get(i) - sortedValues.get(i - 1));12        }13        14        return minDifference;15    }16 17    private void inOrderTraversal(TreeNode node, List<Integer> values) {18        if (node == null) {19            return;20        }21        inOrderTraversal(node.left, values);22        values.add(node.val);23        inOrderTraversal(node.right, values);24    }25}

• Initialize two instance variables: minDifference = Integer.MAX_VALUE and prevNodeValue = null.
• Define a recursive inOrderTraversal helper function.
• Inside the helper function, for a given node: a. If node is null, return. b. Recursively call inOrderTraversal on node.left. c. Process the current node: i. If prevNodeValue is not null, calculate node.val - prevNodeValue and update minDifference = Math.min(minDifference, node.val - prevNodeValue). ii. Update prevNodeValue = node.val. d. Recursively call inOrderTraversal on node.right.
• Call inOrderTraversal(root) from the main function.
• Return minDifference.

The core idea remains the same: the minimum difference will be between two nodes that are adjacent in the sorted order of values. In-order traversal gives us this order. We can perform an in-order traversal and maintain two global or class-level variables: minDifference and prevNodeValue. minDifference is initialized to Integer.MAX_VALUE, and prevNodeValue is initialized to a state indicating it hasn't been set yet (e.g., null or a sentinel value). During the in-order traversal (Left -> Process -> Right): When we process the current node, we first check if prevNodeValue has been set. If it has, we calculate the difference between the current node's value and prevNodeValue. We then update minDifference with the minimum of its current value and this new difference. After processing, we update prevNodeValue to the current node's value. This sets it up for the next node in the in-order sequence. This way, we compare each node with its immediate predecessor in the sorted sequence without storing the entire sequence.

1class Solution {2    private Integer prevNodeValue = null;3    private int minDifference = Integer.MAX_VALUE;4 5    public int minDiffInBST(TreeNode root) {6        inOrderTraversal(root);7        return minDifference;8    }9 10    private void inOrderTraversal(TreeNode node) {11        if (node == null) {12            return;13        }14 15        // Traverse left subtree16        inOrderTraversal(node.left);17 18        // Process current node19        if (prevNodeValue != null) {20            minDifference = Math.min(minDifference, node.val - prevNodeValue);21        }22        prevNodeValue = node.val;23 24        // Traverse right subtree25        inOrderTraversal(node.right);26    }27}