530. Minimum Absolute Difference in BST

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.

Solution:

  • Method 1: BST ```Java /**
    • Definition for a binary tree node.
    • public class TreeNode {
    • int val;
    • TreeNode left;
    • TreeNode right;
    • TreeNode(int x) { val = x; }
    • } */ class Solution { private int res = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { int[] range = getRange(root); return this.res; } private int[] getRange(TreeNode node){ int cur = node.val; int[] left = null, right = null; if(node.left != null){ left = getRange(node.left); this.res = Math.min(res, cur - left[1]); } if(node.right != null){ right = getRange(node.right); this.res = Math.min(res, right[0] - cur); } if(left == null && right == null) return new int[]{cur, cur}; else if(left != null && right != null) return new int[]{left[0], right[1]}; else{ return left == null ? new int[]{cur, right[1]}: new int[]{left[0], cur}; } } } ```