Find the Minimum Absolute Difference in BST Using Java

The question

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note:

• There are at least two nodes in this BST.

The solution

We will start with a stub to build out:

/**
 * 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) {
        
    }
}

Of this, the meat really comes in with the getMinimumDifference method.

So let’s use Depth First Search (DFS) to solve this problem.

/**
 * 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 {
    // Store our list of points
    public List<Integer> list = new ArrayList<>();
    // Store the max differences
    public int dif = Integer.MAX_VALUE;
    
    // Our DFS method
    public void dfs(TreeNode root) {
        // return if not exists
        if(root == null) return;
        // recurse left
        dfs(root.left);
        // add the current node
        list.add(root.val);
        // recurse right
        dfs(root.right);
    }
    // Main entry point, takes in the TreeNode's root
    public int getMinimumDifference(TreeNode root) {
        // do our DFS on the tree
        dfs(root);
        
        // loop through our `list`
        for(int i=1;i<list.size();i++) {
            // primary conditional
            if(Math.abs(list.get(i) - list.get(i - 1)) < dif)
                // set the difference int
                dif = Math.abs(list.get(i) - list.get(i - 1));
        }
        // Return the difference as an integer
        return dif;
    }
}