PROBLEM DESCRIPTION
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.
SOLUTION
We should be aware that the inorder traversal of a BST will be sorted. The minimum absolute value will be a difference in one of the pair of adjacent values in the sorted list of values.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int getMinimumDifference(TreeNode root) {
// Perform an in-order traversal to get the values of the nodes in sorted order
List<Integer> inorder = inorder(root, new ArrayList<>());
// init to max as we are looking for min value
int minAbs = Integer.MAX_VALUE;
// Calculate the minimum absolute difference between adjacent values (it is given that min number of nodes is 2)
for (int i = 1; i < inorder.size(); i++) {
minAbs = Math.min(minAbs, Math.abs(inorder.get(i) - inorder.get(i - 1)));
}
return minAbs;
}
// Recursive function for in-order traversal
public List<Integer> inorder(TreeNode root, List<Integer> list) {
if (root == null) return list;
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
return list;
}
}