LeetCode Solutions Blog

Minimum Distance Between BST Nodes

Number: 799

Difficulty: Easy

Paid? No

Companies: Google, Wix

Problem Description

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

Key Insights

The in-order traversal of a BST produces a sorted list of node values.
The minimum difference will be found between two consecutive values in this sorted sequence.
Use a variable to track the previous node value during traversal.
Update the minimum difference as you visit each node.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the BST, since every node is visited once. Space Complexity: O(n) in the worst-case scenario due to recursion stack (or O(h) where h is the tree height for balanced trees).

Solution

The solution uses an in-order traversal of the BST to get the nodes in a sorted order. As we traverse the tree, we maintain a variable to store the previous node's value. The absolute difference between the current node's value and the previous node's value is computed, and if it is smaller than the current minimum difference, it is updated. This approach leverages the BST's inherent characteristics and ensures that the minimum difference is found efficiently.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        # Initialize variables:
        # prev_val keeps track of the previous node's value.
        # min_diff stores the minimum difference found so far, initialized to a large number.
        self.prev_val = None
        self.min_diff = float('inf')
        
        # Define the in-order traversal function.
        def in_order(node):
            if not node:
                return
            # Traverse left subtree.
            in_order(node.left)
            
            # Process current node:
            if self.prev_val is not None:
                # Update min_diff using the difference with previous node.
                self.min_diff = min(self.min_diff, node.val - self.prev_val)
            # Update the previous value to current node's value.
            self.prev_val = node.val
            
            # Traverse right subtree.
            in_order(node.right)
            
        # Start in-order traversal from the root.
        in_order(root)
        return self.min_diff