What is the Minimum Distance Between BST Nodes problem about?

The problem asks to find the minimum absolute difference between the values of any two distinct nodes in a Binary Search Tree using tree traversal and state tracking.

How do I solve Minimum Distance Between BST Nodes efficiently?

You can solve the problem efficiently using an in-order traversal of the BST while tracking the minimum difference between consecutive nodes.

What traversal method should I use for this problem?

In-order traversal is ideal because it processes the nodes in ascending order, allowing easy calculation of the minimum difference between consecutive nodes.

What is the time complexity of the optimal solution?

The time complexity of the optimal solution is O(n), where n is the number of nodes in the tree, as each node is visited once during the traversal.

Can I improve the space complexity of the solution?

Yes, you can optimize the space complexity by using an iterative in-order traversal to avoid recursion stack overhead, especially for unbalanced trees.

#783

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉搜索树节点最小距离

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。示例 1：输入： root = [4,2,6,1,3] 输出： 1 示例 2：输入： root = [1,0,48,null,null,12,49] 输出： 1 提…

树深度优先搜索广度优先搜索二叉搜索树二叉树

题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

树中节点的数目范围是 [2, 100]
0 <= Node.val <= 10⁵

注意：本题与 530：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 相同

lightbulb

解题思路

方法一：中序遍历

题目需要我们求任意两个节点值之间的最小差值，而二叉搜索树的中序遍历是一个递增序列，因此我们只需要求中序遍历中相邻两个节点值之间的最小差值即可。

我们可以使用递归的方法来实现中序遍历，过程中用一个变量 $\textit{pre}$ 来保存前一个节点的值，这样我们就可以在遍历的过程中求出相邻两个节点值之间的最小差值。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉搜索树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            dfs(root.left)
            nonlocal pre, ans
            ans = min(ans, root.val - pre)
            pre = root.val
            dfs(root.right)

        pre = -inf
        ans = inf
        dfs(root)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of tree traversal techniques, especially in-order traversal.
question_mark
Ensure the candidate is aware of optimizing the algorithm to minimize unnecessary comparisons.
question_mark
Check if the candidate can explain how space complexity relates to the recursive depth of the solution.

warning

常见陷阱

外企场景

error
Failing to recognize that in-order traversal of a BST visits nodes in sorted order.
error
Not optimizing the space complexity when using recursion by improperly handling deep recursion in unbalanced trees.
error
Attempting to compare all pairs of nodes, leading to a brute-force O(n^2) solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider solving the problem iteratively, using a stack to simulate the recursion.
arrow_right_alt
Modify the problem to find the minimum difference in a Binary Tree instead of a Binary Search Tree.
arrow_right_alt
Extend the problem to find the k-th smallest element and its nearest neighbor in a BST.

help

常见问题

外企场景

继续练习

#653 两数之和 IV - 输入二叉搜索树 #530 二叉搜索树的最小绝对差 #449 序列化和反序列化二叉搜索树