Reference: LeetCode
Difficulty: Easy

Problem

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

Note: There are at least two nodes in this BST.

Example:

1
2
3
4
5
6
7
8
Input:
1
\
3
/
2
Output:
1

Analysis

Methods:

  1. Brute-Force
    • Push into a sorted array.
    • Time: $O(N)$
    • Space: $O(N)$
  2. Inorder Traversal
    • We need to use the fact that the tree is a BST and inorder traversal will generate sequence in order.
    • We compare each nodes with the previous if it exists, and update the minimum difference value if necessary.
    • Time: $O(N)$
    • Space: $O(h)$
  3. Preorder Traversal
    • We can apply preorder traversal, but this time when traversing the tree, we update pred if going right, or succ if going left.
    • During visiting the node, we compare the node’s value with pred and succ, and update the minimum difference value if necessary.
    • Time: $O(N)$
    • Space: $O(h)$

Code

Inorder

Note:

  • Initialize prev with null, since we don’t compare at the beginning.
  • Use Math.min instead of comparison operation.
  • Don’t forget to update prev.
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
private int minDiff;
private TreeNode prev;

public int getMinimumDifference(TreeNode root) {
// Assume that root is not null, and there are at least two nodes.
minDiff = Integer.MAX_VALUE;
prev = null;
inorder(root);
return minDiff;
}

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

inorder(x.left);

if (prev != null) { // compare
int newMin = Math.abs(prev.val - x.val);
minDiff = Math.min(minDiff, newMin);
}
prev = x; // update prev

inorder(x.right);
}

Preorder

Note:

  • Initialize pred and succ with null.
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
private int minDfff;

public int getMinimumDifference(TreeNode root) {
minDiff = Integer.MAX_VALUE;
traverse(root, null, null);
return minDiff;
}

private void traverse(TreeNode x, TreeNode pred, TreeNode succ) {
if (x == null) {
return;
}

if (pred != null) {
int newMin = Math.abs(pred.val - x.val);
minDiff = Math.min(minDiff, newMin);
}

if (succ != null) {
int newMin = Math.abs(succ.val - x.val);
minDiff = Math.min(minDiff, newMin);
}

traverse(x.left, pred, x); // go left
traverse(x.right, x, succ); // go right
}

Comment