#530

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Minimum Absolute Difference in BST

Find the minimum absolute difference between values of any two nodes in a BST using tree traversal and careful state tracking.

tree depth first search breadth first search binary search tree binary tree

Problem Statement

Given the root of a Binary Search Tree (BST), determine the minimum absolute difference between values of any two different nodes. You must account for all node pairs and optimize traversal to avoid redundant comparisons.

The BST nodes have integer values, and the tree contains at least two nodes. Implement a solution that efficiently computes the minimum absolute difference while leveraging BST ordering properties and tree traversal patterns.

Examples

Example 1

Input: root = [4,2,6,1,3]

Output: 1

Example details omitted.

Example 2

Input: root = [1,0,48,null,null,12,49]

Output: 1

Example details omitted.

Constraints

The number of nodes in the tree is in the range [2, 104].
0 <= Node.val <= 105

Solution Approach

In-order DFS traversal

Perform an in-order depth-first search (DFS) to visit nodes in ascending order. Track the previous node value and compute the absolute difference with the current node, updating the minimum difference found so far. This approach leverages BST ordering to only compare consecutive values.

Iterative DFS using stack

Use an explicit stack to traverse the BST iteratively in in-order sequence. Maintain previous node value and current minimum difference as state variables. This avoids recursion stack overhead and is practical for large BSTs where recursion depth might be a concern.

BFS with level tracking

While less conventional, a BFS can track all node values and sort them to compute differences. Maintain a list of visited node values and update the minimum absolute difference by comparing each pair. This approach demonstrates state tracking flexibility, though in-order DFS is more efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Inorder Traversal

The problem requires us to find the minimum difference between the values of any two nodes. Since the inorder traversal of a binary search tree is an increasing sequence, we only need to find the minimum difference between the values of two adjacent nodes in the inorder traversal.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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

Continue Practicing

#449 serialize and deserialize bst #653 two sum iv input is a bst #783 minimum distance between bst nodes