Minimum Distance Between Bst Nodes - Leetcode Solution

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.

1