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
}