⚡Flashcard Drill➔
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.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems

中文速览与面试要点

二叉搜索树节点最小距离

给你一个二叉搜索树的根节点 root,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。约束:树中节点的数目范围是 [2, 100];0 ≤ Node.val ≤ 10^5。

核心要点

  • 中序遍历 + 相邻比较(标准解) :BST 的中序遍历是升序序列,因此最小差值必然出现在 相邻 两个节点之间。
  • 实现 :递归中序,用变量 prev 记录前一个访问的值,每步用 node.val − prev 更新最优。
  • 为什么只需比较相邻 :升序序列中,任意两数的差至少为它们之间相邻差之和,因此最小值必在相邻对中取得。
  • 复杂度 :O(n) 时间、O(h) 空间。

常见陷阱

  • 比较所有节点对 :O(n²)。中序相邻比较即可。
  • 忘记 prev is not None 的判断 :第一个节点没有前驱。
  • prev 忘记用 nonlocal 声明 :会创建局部变量,导致每层递归各自独立。
  • 用 abs(node.val − prev) :中序升序,差必为正,无需取绝对值。

参考实现

class Solution:
    def minDiffInBST(self, root: 'TreeNode') -> int:
        prev = None
        best = float('inf')

        def inorder(node):
            nonlocal prev, best
            if not node:
                return
            inorder(node.left)
            if prev is not None:
                diff = node.val - prev          # 中序升序,差必为正
                if diff < best:
                    best = diff
            prev = node.val
            inorder(node.right)

        inorder(root)
        return best