# 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 <= 10`

^{5}

**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 `minDiffInBST`

function 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:

- 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. - It recursively calls itself with the left subtree of the current node (
`root->left`

), which effectively traverses the left subtree. - 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`

. - 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". - 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.