## Similar Problems

Similar Problems not available

# Minimum Distance Between Bst Nodes - Leetcode Solution

## Companies:

LeetCode: Minimum Distance Between Bst Nodes Leetcode Solution

Difficulty: Easy

Topics: binary-search-tree depth-first-search breadth-first-search tree binary-tree

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.

## Minimum Distance Between Bst Nodes Solution Code

`1`