💬 Discord
Sign In
NeetCode #430LC-783EasyTrees
← Back to All Problems

#430 · #783 · Minimum Distance Between BST Nodes(二叉搜索树节点最小距离)

📌 Problem Statement & Constraints

Given the root of a binary search tree, return the minimum difference between the values of any two distinct nodes. Constraints: the number of nodes is in [2, 100], 0 <= Node.val <= 10^5.

💡 Core Algorithmic Approaches

  1. An in-order traversal of a BST visits the values in ascending order.
  2. The minimum difference must therefore occur between adjacent values in that order.
  3. Track the previous visited value and update the minimum gap.
  4. This is O(n) instead of the O(n log n) sort-the-values approach.

💻 Benchmark Python3 Implementation

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        self.prev = None
        self.best = float("inf")

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            if self.prev is not None:
                self.best = min(self.best, node.val - self.prev)   # adjacent pair
            self.prev = node.val
            inorder(node.right)

        inorder(root)
        return self.best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one in-order traversal.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing all pairs: O(n^2), and unnecessary given the sorted order.
  • Sorting the values and scanning: O(n log n); the in-order traversal already yields the sorted order.
  • Forgetting the prev is not None guard: the first visited node has no predecessor.
  • Assuming the tree is balanced: the recursion depth can reach n for a degenerate BST.