Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3]
Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49]
Output: 1
Constraints:
- The number of nodes in the tree is in the range [2, 104].
- 0 <= Node.val <= 105
My Solution
We can solve this problem by doing an inorder traversal to get a sorted array of all the tree’s values. Then we just iterate through every pair of values and update the minimum absolute difference.
Time complexity is O(n), where n is the number of nodes in the tree because we must do two passes through all elements, one to do the inorder traversal and the other to iterate through the sorted array of values. Space complexity is O(n) because of the space required for the array of values.
/**
* 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) {
List<Integer> vals = new ArrayList<>();
int min = Integer.MAX_VALUE;
inorder(root, vals);
for (int i = 1; i < vals.size(); i++) {
min = Math.min(min, vals.get(i) - vals.get(i-1));
}
return min;
}
public void inorder(TreeNode root, List<Integer> vals) {
if (root == null) {
return;
}
inorder(root.left, vals);
vals.add(root.val);
inorder(root.right, vals);
}
}