What is the best approach to find Minimum Absolute Difference in BST?

An in-order DFS traversal is most efficient, as it visits nodes in sorted order and only compares consecutive values to find the minimum difference.

Can BFS be used to solve this problem efficiently?

Yes, BFS can be used if you track all node values and sort them before computing differences, but it is generally less space-efficient than in-order DFS.

How do I handle large BSTs without hitting recursion limits?

Use iterative DFS with a stack to traverse the tree in-order, maintaining previous node and minimum difference state explicitly.

Does this method work if the BST contains duplicate values?

Yes, duplicates are handled naturally in in-order traversal; the minimum absolute difference may be zero if consecutive nodes have equal values.

Why track only previous node value instead of all nodes?

In-order DFS ensures nodes are visited in ascending order, so the minimum difference will always occur between consecutive nodes, avoiding unnecessary comparisons.

#530

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, 10⁴]
0 <= Node.val <= 10⁵

注意：本题与 783 https://leetcode.cn/problems/minimum-distance-between-bst-nodes/ 相同

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 getMinimumDifference(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

复杂度分析

指标	值
时间	complexity is O(n) for in-order DFS as each node is visited once. Space complexity is O(h) for recursion stack or iterative stack, where h is tree height. BFS may require O(n) additional space for storing values.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you tracking previous values correctly during traversal to avoid missing minimum differences?
question_mark
Can you implement in-order traversal both recursively and iteratively?
question_mark
Do you consider the BST property to reduce comparisons instead of brute-force checking all pairs?

warning

常见陷阱

外企场景

error
Comparing all pairs of nodes leads to O(n^2) time complexity instead of leveraging BST ordering.
error
Forgetting to initialize previous node value can cause incorrect difference computation on the first node.
error
Using BFS without proper sorting or state tracking may miss the minimum absolute difference.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the minimum absolute difference in a Binary Tree without BST ordering, requiring full pairwise comparisons.
arrow_right_alt
Find the maximum absolute difference between BST nodes, changing comparison logic but using similar traversal techniques.
arrow_right_alt
Compute the minimum absolute difference for a BST with duplicate values, requiring careful handling of equal consecutive nodes.

help

常见问题

外企场景

继续练习

#449 序列化和反序列化二叉搜索树 #653 两数之和 IV - 输入二叉搜索树 #783 二叉搜索树节点最小距离