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

- Initialize a variable called min_diff to infinity.
- Initialize a variable called prev_val to null.
- Traverse the BST in in-order.
- 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.
- Update prev_val to the current node’s value.
- 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) { // your code here };

/** * 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; stackstk; 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 Listinorder = 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); inorder.Add(root.val); InOrder(root.right, inorder); } }