530 Minimum Absolute Difference in BST

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.

Complexity: O(n) time O(N) space

The Idea: If we run an in order traversal through the tree, the minimum difference is guaranteed to be between two adjacent elements. So that is what we do while maintaining the minimum value.

int getMinimumDifference(TreeNode* root) {
    int prev = INT_MAX, my_min = INT_MAX;
    getMinimumDifferenceRec(root, prev, my_min);
    return my_min;
}

void getMinimumDifferenceRec(TreeNode* root, int &prev, int &my_min) {
    if (root) {
        getMinimumDifferenceRec(root->left, prev, my_min);
        my_min = min(my_min, abs(root->val - prev));
        prev = root->val;
        getMinimumDifferenceRec(root->right, prev, my_min);
    }
}