LeetCode: 530. Minimum Absolute Difference in BST

The Problem

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example

Input:  [1,0,48,null,null,12,49]
Output: 1

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

int getMinimumDifference(TreeNode* root) {
    int minDiff = INT_MAX;
    TreeNode *prev = nullptr;
    getMinimumDifference(root, prev, minDiff);
    return minDiff;
}

void getMinimumDifference(TreeNode* root, TreeNode *&prev, int &minDiff) {
    if (root == nullptr) return;

    TreeNode *left = root->left;
    getMinimumDifference(left, prev, minDiff);

    if (prev != nullptr) 
    	minDiff = min(minDiff, abs(root->val - prev->val));

    prev = root;

    TreeNode *right = root->right;
    getMinimumDifference(right, prev, minDiff);
        
}

Here's what's happening:

1. The function is recursively traversing the Binary tree using an in-order traversal approach. In-order traversal means visiting the left subtree, the current node, and then the right subtree.
2. It takes three parameters: root is the current node being considered, prev is a pointer to the previously visited node, and minDiff is a reference to the minimum absolute difference being calculated.
3. If the current root node is nullptr (which is the base case for a leaf node or an empty subtree), the function returns immediately.
4. It first recursively traverses the left subtree by calling getMinimumDifference(left, prev, minDiff).
5. After the left subtree is traversed, it compares the absolute difference between the current node's value and the previous node's value with the current minimum difference. If it's smaller, it updates minDiff accordingly.
6. The prev pointer is then updated to the current node, as it will become the previous node for the next iteration.
7. Finally, it recursively traverses the right subtree by calling getMinimumDifference(right, prev, minDiff).

The key idea here is that by performing an in-order traversal of the Binary tree and keeping track of the previous node, you can efficiently find the minimum absolute difference between any two different nodes in the tree.