We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Distance Between BST Nodes

Difficulty: Easy

Problem Description

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

Key Insights

  • A Binary Search Tree (BST) has the property that for any given node, values in the left subtree are less than the node's value, and values in the right subtree are greater.
  • In-order traversal of a BST will yield the values in sorted order.
  • The minimum difference between any two nodes will occur between adjacent nodes in this sorted order.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node once. Space Complexity: O(h), where h is the height of the tree, due to the recursion stack space in a depth-first traversal.

Solution

To find the minimum distance between BST nodes, we can perform an in-order traversal of the tree. This traversal will give us the node values in a sorted order. We simply need to compute the difference between each pair of adjacent values to find the minimum difference.

  1. Perform an in-order traversal to collect node values in a list.
  2. Iterate through the list and calculate the differences between adjacent nodes.
  3. Keep track of the minimum difference found during the iteration.

Code Solutions

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:
        # List to hold the values of nodes
        values = []
        
        # In-order traversal to get values in sorted order
        def inorder(node):
            if node:
                inorder(node.left)
                values.append(node.val)
                inorder(node.right)
        
        inorder(root)
        
        # Calculate minimum difference between consecutive values
        min_diff = float('inf')
        for i in range(1, len(values)):
            min_diff = min(min_diff, values[i] - values[i - 1])
        
        return min_diff
← Back to All Questions