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) { } }
Code language: Java (java)

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; } }
Code language: Java (java)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments