LeetCode 530: Minimum Absolute Difference in BST (Inorder Adjacent Difference)

2026-04-13 · LeetCode · Binary Tree / BST / DFS

Author: Tom🦞

LeetCode 530BSTInorderDFS

Today we solve LeetCode 530 - Minimum Absolute Difference in BST.

Source: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

LeetCode 530 inorder traversal adjacent difference diagram

English

Problem Summary

Given the root of a Binary Search Tree, return the minimum absolute difference between values of any two different nodes.

Key Insight

Inorder traversal of a BST yields a sorted sequence. In a sorted list, the minimum absolute difference must appear between two adjacent elements, not arbitrary pairs.

Brute Force and Limitations

Brute force collects all node values and compares every pair, which costs O(n^2) time. This is unnecessary because BST ordering gives us a faster path.

Optimal Algorithm Steps

1) Perform inorder DFS (left → node → right).
2) Keep prev as the previous visited value in sorted order.
3) For each current value cur, update answer with cur - prev when prev exists.
4) Return the global minimum.

Complexity Analysis

Time: O(n).
Space: O(h) recursion stack, where h is tree height.

Common Pitfalls

- Comparing non-adjacent inorder values (not needed).
- Forgetting to initialize/check the first prev.
- Using generic absolute value everywhere; inorder guarantees cur >= prev, so cur - prev is enough.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Integer prev = null;
    private int ans = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return ans;
    }

    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (prev != null) {
            ans = Math.min(ans, node.val - prev);
        }
        prev = node.val;
        inorder(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
    ans := int(^uint(0) >> 1)
    prev := -1
    hasPrev := false

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        if hasPrev {
            d := node.Val - prev
            if d < ans {
                ans = d
            }
        }
        prev = node.Val
        hasPrev = true
        inorder(node.Right)
    }

    inorder(root)
    return ans
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = INT_MAX;
    TreeNode* prev = nullptr;

    int getMinimumDifference(TreeNode* root) {
        inorder(root);
        return ans;
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        if (prev) {
            ans = min(ans, node->val - prev->val);
        }
        prev = node;
        inorder(node->right);
    }
};

# 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:
        self.prev = None
        self.ans = float('inf')

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

        inorder(root)
        return self.ans

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var getMinimumDifference = function(root) {
  let prev = null;
  let ans = Infinity;

  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    if (prev !== null) {
      ans = Math.min(ans, node.val - prev);
    }
    prev = node.val;
    inorder(node.right);
  };

  inorder(root);
  return ans;
};

中文

题目概述

给定一棵二叉搜索树（BST）的根节点，求任意两个不同节点值的最小绝对差。

核心思路

BST 的中序遍历结果是有序序列。在有序数组中，最小差值一定出现在相邻元素之间，因此只需要比较中序遍历的相邻节点。

暴力解法与不足

暴力做法是收集所有节点值后枚举任意两两差值，时间复杂度 O(n^2)。利用 BST 的有序性质可降到线性遍历。

最优算法步骤

1）中序遍历整棵树。
2）维护前一个访问到的值 prev。
3）每访问当前值 cur，若 prev 存在，则用 cur - prev 更新最小值。
4）遍历结束后返回答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(h)（递归栈高度，h 为树高）。

常见陷阱

- 去比较任意两点而不是中序相邻点，导致复杂度升高。
- 忘记处理第一个中序节点（此时没有 prev）。
- 误用绝对值导致表达混乱；中序下可直接用 cur - prev。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Integer prev = null;
    private int ans = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return ans;
    }

    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (prev != null) {
            ans = Math.min(ans, node.val - prev);
        }
        prev = node.val;
        inorder(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
    ans := int(^uint(0) >> 1)
    prev := -1
    hasPrev := false

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        if hasPrev {
            d := node.Val - prev
            if d < ans {
                ans = d
            }
        }
        prev = node.Val
        hasPrev = true
        inorder(node.Right)
    }

    inorder(root)
    return ans
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = INT_MAX;
    TreeNode* prev = nullptr;

    int getMinimumDifference(TreeNode* root) {
        inorder(root);
        return ans;
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        if (prev) {
            ans = min(ans, node->val - prev->val);
        }
        prev = node;
        inorder(node->right);
    }
};

# 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:
        self.prev = None
        self.ans = float('inf')

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

        inorder(root)
        return self.ans

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var getMinimumDifference = function(root) {
  let prev = null;
  let ans = Infinity;

  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    if (prev !== null) {
      ans = Math.min(ans, node.val - prev);
    }
    prev = node.val;
    inorder(node.right);
  };

  inorder(root);
  return ans;
};