LeetCode: 783. Minimum Distance Between BST Nodes

The Problem

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

Example

Input:  [4,2,6,1,3]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• 0 <= Node.val <= 105

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 minDiffInBST(TreeNode* root) {
    int minDiff = INT_MAX, lastNode = -1;
    minDiffInBST(root, minDiff, lastNode);
    return minDiff;
}

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

    minDiffInBST(root->left, minDiff, lastNode);

    if (lastNode != -1 ) {
        int currentDiff = abs(root->val - lastNode);
        minDiff = min(minDiff, currentDiff);
    }

    lastNode = root->val;

    minDiffInBST(root->right, minDiff, lastNode);
}

This helper minDiffInBSTfunction is responsible for the in-order traversal of the BST and calculating the minimum difference between node values. Let's break down what it does step by step:

1. It checks if the current node (root) is nullptr, which means the current subtree is empty. If it's empty, the function returns without doing anything.
2. It recursively calls itself with the left subtree of the current node (root->left), which effectively traverses the left subtree.
3. If lastNode is not -1 (meaning this isn't the first node), it calculates the absolute difference between the current node's value (root->val) and the value of the last visited node (lastNode). It then updates minDiff if this current difference is smaller than the current minDiff.
4. It updates lastNode to the current node's value. This prepares for the next iteration of the traversal, where the current node will be considered the "last node".
5. It recursively calls itself with the right subtree of the current node (root->right), effectively traversing the right subtree.

The combination of these steps, along with the in-order traversal, ensures that the function iterates through the BST's nodes in ascending order. This way, it can calculate the differences between adjacent nodes' values and keep track of the smallest difference encountered. The final result is stored in minDiff, which is returned to the main function.