# Solution For Minimum Distance Between Bst Nodes

Problem Statement:

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

Solution:

Approach:

The idea here is to traverse the BST in in-order, which will give us a sorted sequence. While traversing the in-order sequence, we can keep track of the minimum difference between adjacent nodes.

Algorithm:

1. Initialize a variable called min_diff to infinity.
2. Initialize a variable called prev_val to null.
3. Traverse the BST in in-order.
4. For each node, calculate the absolute difference between its value and the prev_val variable. If this absolute difference is less than min_diff, update min_diff to this value.
5. Update prev_val to the current node’s value.
6. Return the final value of min_diff.

Code:

Here is the code implementation of the above algorithm in Python:

“`
class Solution:
def minDiffInBST(self, root: TreeNode) -> int:
# Initialize min_diff to infinity
min_diff = float(“inf”)
# Initialize prev_val to null
prev_val = None

``````    # Define a recursive function to traverse the BST in in-order
def traverse(node):
nonlocal min_diff, prev_val
# Base case: if node is null, return
if not node:
return
# Traverse left subtree
traverse(node.left)
# Check the difference between current node's value and prev_val
if prev_val is not None:
diff = abs(node.val - prev_val)
if diff < min_diff:
min_diff = diff
# Update prev_val to current node's value
prev_val = node.val
# Traverse right subtree
traverse(node.right)

# Call the recursive function on the root node
traverse(root)

# Return the final value of min_diff
return min_diff
``````

“`

Time Complexity:

The time complexity of this algorithm is O(N), where N is the number of nodes in the BST. This is because we traverse each node exactly once.

Space Complexity:

The space complexity of this algorithm is O(H), where H is the height of the BST. This is because we use a recursive function to traverse the BST, and the maximum depth of the recursive call stack is equal to the height of the BST.

## Step by Step Implementation For Minimum Distance Between Bst Nodes

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public int minDiffInBST(TreeNode root) {
// Base case
if (root == null) {
return 0;
}

// Recursive case 1: If the root has no left child,
// then the minimum difference must be between the root and its right child's value
if (root.left == null) {
return minDiffInBST(root.right);
}

// Recursive case 2: If the root has no right child,
// then the minimum difference must be between the root and its left child's value
if (root.right == null) {
return minDiffInBST(root.left);
}

// Recursive case 3: If the root has both left and right children,
// then the minimum difference must be either between the root and its left child's value
// or between the root and its right child's value, whichever is smaller
return Math.min(minDiffInBST(root.left), minDiffInBST(root.right));
}
}```
`This problem can be solved by doing a level-order traversal of the BST. We can keep track of the previous node at each level, and calculate the minimum distance between the current node and the previous node.`
```/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDiffInBST = function(root) {
};```
```/**
* 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 {
public:
int minDiffInBST(TreeNode* root) {
int minDiff = INT_MAX;
stack stk;
TreeNode* cur = root;
TreeNode* prev = NULL;
while (!stk.empty() || cur) {
while (cur) {
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
if (prev) {
minDiff = min(minDiff, abs(prev->val - cur->val));
}
prev = cur;
cur = cur->right;
}
return minDiff;
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int MinDiffInBST(TreeNode root) {
//inorder traversal of BST gives us sorted array
List inorder = new List();
InOrder(root, inorder);

//minimum difference will be between adjacent elements in sorted array
int minDiff = int.MaxValue;
for(int i = 0; i < inorder.Count - 1; i++){
minDiff = Math.Min(minDiff, inorder[i+1] - inorder[i]);
}

return minDiff;
}

public void InOrder(TreeNode root, List inorder){
if(root == null) return;

InOrder(root.left, inorder);