Minimum Absolute Difference in BST

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

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5/**6 * Definition for a binary tree node.7 * public class TreeNode {8 *     int val;9 *     TreeNode left;10 *     TreeNode right;11 *     TreeNode() {}12 *     TreeNode(int val) { this.val = val; }13 *     TreeNode(int val, TreeNode left, TreeNode right) {14 *         this.val = val;15 *         this.left = left;16 *         this.right = right;17 *     }18 * }19 */20class Solution {21    public int getMinimumDifference(TreeNode root) {22        List<Integer> values = new ArrayList<>();23        collectValues(root, values);24        25        Collections.sort(values);26        27        int minDiff = Integer.MAX_VALUE;28        for (int i = 1; i < values.size(); i++) {29            minDiff = Math.min(minDiff, values.get(i) - values.get(i - 1));30        }31        return minDiff;32    }33 34    private void collectValues(TreeNode node, List<Integer> values) {35        if (node == null) {36            return;37        }38        values.add(node.val);39        collectValues(node.left, values);40        collectValues(node.right, values);41    }42}

• Create an empty list values.
• Define a helper function collectValues(node, list) that recursively traverses the tree and adds each node's value to the list.
• Call collectValues(root, values) to populate the list.
• Initialize minDiff to Integer.MAX_VALUE.
• Use a nested loop to iterate through all pairs of indices (i, j) where j > i.
• For each pair, calculate diff = Math.abs(values.get(i) - values.get(j)).
• Update minDiff = Math.min(minDiff, diff).
• Return minDiff.

First, we perform a traversal (like pre-order) of the entire BST to gather all the node values and store them in a list. Then, we use two nested loops to iterate through all unique pairs of values in the list. For each pair (list[i], list[j]), we calculate their absolute difference abs(list[i] - list[j]). We maintain a variable, minDifference, initialized to a very large value. We update this variable whenever we find a smaller difference. After checking all pairs, minDifference will hold the minimum absolute difference. This method does not utilize the properties of a BST, making it inefficient for this problem.

1import java.util.ArrayList;2import java.util.List;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    public int getMinimumDifference(TreeNode root) {21        List<Integer> values = new ArrayList<>();22        collectValues(root, values);23        24        int minDiff = Integer.MAX_VALUE;25        for (int i = 0; i < values.size(); i++) {26            for (int j = i + 1; j < values.size(); j++) {27                minDiff = Math.min(minDiff, Math.abs(values.get(i) - values.get(j)));28            }29        }30        return minDiff;31    }32 33    private void collectValues(TreeNode node, List<Integer> values) {34        if (node == null) {35            return;36        }37        values.add(node.val);38        collectValues(node.left, values);39        collectValues(node.right, values);40    }41}

• Initialize two instance variables: prevValue to null and minDifference to Integer.MAX_VALUE.
• Define a recursive helper function inOrderTraversal(node).
• Inside the helper function:
  • Base case: If node is null, return.
  • Recursively call inOrderTraversal(node.left).
  • Process the current node:
    • If prevValue is not null, calculate node.val - prevValue and update minDifference if this difference is smaller.
    • Set prevValue = node.val.
  • Recursively call inOrderTraversal(node.right).
• Call inOrderTraversal(root) from the main function.
• Return minDifference.

An in-order traversal (Left -> Root -> Right) on a BST processes the nodes in a sorted sequence. This means that the minimum difference between any two nodes must be between two nodes that are adjacent in the in-order traversal sequence. We can perform a recursive in-order traversal. We use a global or member variable prevValue to store the value of the previously visited node and minDifference to store the minimum difference found so far. The traversal function works as follows:

1. Recursively traverse the left subtree.
2. When visiting the current node, if prevValue is not null (i.e., this is not the first node in the traversal), calculate the difference currentNode.val - prevValue. Update minDifference with this value if it's smaller.
3. Update prevValue to the current node's value.
4. Recursively traverse the right subtree. This way, we compare each node with its immediate predecessor in the sorted sequence, guaranteeing we find the minimum difference without needing to store all values or sort them explicitly.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private Integer prevValue = null;18    private int minDifference = Integer.MAX_VALUE;19 20    public int getMinimumDifference(TreeNode root) {21        inOrderTraversal(root);22        return minDifference;23    }24 25    private void inOrderTraversal(TreeNode node) {26        if (node == null) {27            return;28        }29 30        // Traverse left subtree31        inOrderTraversal(node.left);32 33        // Process current node34        if (prevValue != null) {35            minDifference = Math.min(minDifference, node.val - prevValue);36        }37        prevValue = node.val;38 39        // Traverse right subtree40        inOrderTraversal(node.right);41    }42}