530. Minimum Absolute Difference in BST (Easy)

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.

Follow Up: What if it is not a BST? (Follow up of the problem) The idea is to put values in a TreeSet and then every time we can use O(lgN) time to lookup for the nearest values.

Solution 1: Inorder Traverse

In-Order traverse, time complexity O(N), space complexity O(h).

version 1: 22ms

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    void inorder(TreeNode* root, int& prev, int& res) {
        if (!root) return;
        inorder(root->left, prev, res);
        if (prev != -1) res = min(res, root->val-prev);
        prev = root->val;
        inorder(root->right, prev, res);
    }
public:
    int getMinimumDifference(TreeNode* root) {
        int res = INT_MAX, prev = -1;
        inorder(root, prev, res);
        return res;
    }
};

version 2: 19ms

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        if (!root) return diff;
        getMinimumDifference(root->left);
        if (prev != -1) diff = min(diff, root->val-prev);
        prev = root->val;
        getMinimumDifference(root->right);
        return diff;
    }
private:
    int diff = INT_MAX;
    int prev = -1;
};

Solution 2:

Pre-Order traverse, time complexity O(NlgN), space complexity O(N).

public class Solution {
    TreeSet<Integer> set = new TreeSet<>();
    int min = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;

        if (!set.isEmpty()) {
            if (set.floor(root.val) != null) {
                min = Math.min(min, Math.abs(root.val - set.floor(root.val)));
            }
            if (set.ceiling(root.val) != null) {
                min = Math.min(min, Math.abs(root.val - set.ceiling(root.val)));
            }
        }

        set.add(root.val);

        getMinimumDifference(root.left);
        getMinimumDifference(root.right);

        return min;
    }
}

Note!

seems like if the tree were not a BST you could just as easily add the values to an array and sort the array, then do the O(n) pass to find min diff. Not sure the tree set has any advantage. What do you think? Thanks!