Leetcode – Minimum Distance Between BST Nodes Solution in Python

Spread the love

Binary Search Trees (BSTs) are a cornerstone data structure in computer science, often found at the heart of many algorithms and programming problems. One such captivating problem on platforms like Leetcode revolves around determining the minimum distance (difference) between nodes in a BST. This article offers an exhaustive exploration of the “Minimum Distance Between BST Nodes” problem, diving into its intricacies and providing a Pythonic solution.

Problem Statement

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

Note:

  • The BST is populated with unique values.
  • There are at least two nodes in the BST.

Example:

Input: root = [4,2,6,1,3]
Output: 1

Understanding the Problem

In the given problem, you’re essentially tasked with finding the two nodes in the BST whose difference is the smallest. Given the properties of a BST — where left children are smaller than their parents and right children are larger — this problem becomes an exercise in in-order traversal.

When you traverse a BST in-order (left, root, right), the nodes are visited in ascending order. The minimum distance would, therefore, be the smallest difference between consecutive nodes in this traversal.

Solution Approaches

In-Order Traversal Approach

  1. Perform an in-order traversal of the BST, storing the result in a list.
  2. Iterate through the list and determine the minimum difference between consecutive elements.

This approach, while intuitive and straightforward, requires additional space proportional to the number of nodes in the tree.

Optimized In-Order Traversal Approach

Instead of storing the entire traversal, we can keep track of the previous node and calculate the difference on-the-fly. This way, we don’t need the extra space for the entire list, only for a couple of variables.

  1. Initialize a variable (prev) to store the previous node’s value and another (min_diff) to store the minimum difference found so far.
  2. Perform an in-order traversal. For each node:
    • Calculate the difference between the current node’s value and prev.
    • Update min_diff if this difference is smaller.
    • Set prev to the current node’s value.
  3. Return min_diff.

Python Solutions

In-Order Traversal Solution:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDiffInBST(root: TreeNode) -> int:
    def in_order(node):
        return in_order(node.left) + [node.val] + in_order(node.right) if node else []

    values = in_order(root)
    return min(values[i+1] - values[i] for i in range(len(values) - 1))

# Example Usage
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(minDiffInBST(root))  # Expected output: 1

Optimized In-Order Traversal Solution:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDiffInBST(root: TreeNode) -> int:
    prev = float('-inf')
    min_diff = float('inf')
    
    def in_order(node):
        nonlocal prev, min_diff
        if not node:
            return
        in_order(node.left)
        min_diff = min(min_diff, node.val - prev)
        prev = node.val
        in_order(node.right)

    in_order(root)
    return min_diff

# Example Usage
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(minDiffInBST(root))  # Expected output: 1

Complexity Analysis

In-Order Traversal Solution:

Time Complexity: O(n) where n is the number of nodes in the tree. This is due to the in-order traversal.

Space Complexity: O(n) because we store the values of all nodes in a list.

Optimized In-Order Traversal Solution:

Time Complexity: O(n) since we still perform an in-order traversal.

Space Complexity: O(h) where h is the height of the BST. This accounts for the recursion stack during the traversal. In the worst case (a skewed tree), this would be O(n), but for a balanced BST, it would be O(log n).

Conclusion

The “Minimum Distance Between BST Nodes” problem exemplifies the power of understanding the inherent properties of data structures, like the BST. By recognizing the ordered nature of the in-order traversal, we can efficiently tackle the problem without resorting to exhaustive searches or complex algorithms. This problem also underscores the importance of iterative optimization: starting with a simple solution and then refining it to improve space or time complexity.

Leave a Reply