[LeetCode] Problem 530 - Minimum Absolute Difference in BST

Posted on | In ,

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

Example

Input:

1
2
3
4
5
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.

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private int min = Integer.MAX_VALUE;
private int prev = -1;

public int getMinimumDifference(TreeNode root) {
    inorder(root);
    return min;
}

private void inorder(TreeNode root) {
    if (root == null)
        return;

    inorder(root.left);

    if (prev != -1)
        min = Math.min(min, root.val - prev);

    prev = root.val;

    inorder(root.right);
}