Domain 1EasyCORE

Minimum Distance Between BST Nodes

The problem asks us to find the minimum difference between the values of any two different nodes in a Binary Search Tree (BST). The input is the root of the BST, and the output should be an integer representing the minimum difference. The constraints specify that the number of nodes in the tree ranges from 2 to 100, and each node's value is between 0 and 10^5.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Recursion

783. Minimum Distance Between BST Nodes

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Recursion
FAANG asked: 1
Acceptance rate: 54.2%


Problem Breakdown

The problem asks us to find the minimum difference between the values of any two different nodes in a Binary Search Tree (BST). The input is the root of the BST, and the output should be an integer representing the minimum difference. The constraints specify that the number of nodes in the tree ranges from 2 to 100, and each node’s value is between 0 and 10^5.

Intuition

A brute-force approach would involve comparing every pair of nodes in the tree, which would result in a time complexity of O(n^2), where n is the number of nodes. This is inefficient for larger trees. The key insight is to leverage the properties of a BST: an in-order traversal of a BST yields the node values in sorted order. By performing an in-order traversal, we can easily compute the minimum difference between consecutive nodes, which will give us the desired result.

Approach

  1. Perform an in-order traversal of the BST to get the node values in sorted order.
  2. Initialize a variable min_diff with a large value (e.g., infinity).
  3. Iterate through the sorted list of node values and compute the difference between each pair of consecutive nodes.
  4. Update min_diff if a smaller difference is found.
  5. Return min_diff.

Complexity Analysis

  • Time complexity: O(n), where n is the number of nodes in the tree. This is because we perform a single in-order traversal of the tree.
  • Space complexity: O(n) due to the storage required for the list that holds the node values in sorted order.

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:
    # Helper function to perform in-order traversal and collect node values
    def inorder_traversal(node):
        if not node:
            return []
        return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)
    
    # Get the sorted list of node values
    sorted_values = inorder_traversal(root)
    
    # Initialize the minimum difference with a large value
    min_diff = float('inf')
    
    # Compute the minimum difference between consecutive nodes
    for i in range(1, len(sorted_values)):
        min_diff = min(min_diff, sorted_values[i] - sorted_values[i - 1])
    
    return min_diff

Edge Cases Handled

  • Minimum number of nodes: The problem guarantees at least two nodes, so the code does not need to handle fewer than two nodes.
  • Maximum node value: The maximum value for a node is 10^5, which is within the range of standard integer operations in Python.
  • Balanced vs. unbalanced tree: The approach works regardless of whether the tree is balanced or unbalanced, as it relies on the sorted order of node values obtained from an in-order traversal.

The solution provided is correct and efficient. It leverages the properties of a BST to perform an in-order traversal, which results in a sorted list of node values. By computing the differences between consecutive nodes in this sorted list, we can find the minimum difference efficiently. The time complexity is O(n), where n is the number of nodes, and the space complexity is also O(n) due to the storage required for the sorted list.