Minimum Absolute Difference in BST

Problem

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

Example:

Input:

   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.

Solution

Inorder O(n) solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int min = Integer.MAX_VALUE;
    Integer prev = null; //we need to check null, so init with Integer not int

    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        getMinimumDifference(root.left);
        if (prev != null) min = Math.min(min, root.val - prev); //cause root is right and prev is left, so the difference is always positive in BST
        prev = root.val;
        getMinimumDifference(root.right);
        return min;
    }
}

Analysis

Since this is a BST, we know the min difference must be in adjacent nodes
Hence we use inorder traversal to get the result
We don't have to init prev as TreeNode because we just need its val
We go through the left, and then set current node.val as prev
Then we check the right node and update the min

Complexity

• Time: O(n), where n is the number of nodes in BST. In worst case, we have to traversal all nodes
• Space: O(1), only constant space is used