LeetCode 530: Minimum Absolute Difference in BST

Meta Data

#

Difficulty: easy First Attempt: 2022-08-25

• Submissions: Accepted ×2

Approach

#

A BST’s in-order traversal is sorted, and in a sorted sequence the closest pair is adjacent (Tree Template 3). Remember the previous value during the in-order walk and update the answer with each difference. This is the same problem as LC 783.

My Solution

#

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        best, prev = float("inf"), None
        stack, cur = [], root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            if prev is not None:
                best = min(best, cur.val - prev)
            prev = cur.val
            cur = cur.right
        return best

Complexity

#

Time O(n), space O(h).

Mistakes to Avoid

#

• The closest values need not be parent and child; compare in-order neighbors.

Interview Explanation

#

A BST’s in-order is sorted and the minimum difference lies between neighbors, so I keep the previous value during the in-order walk and update the minimum. Time O(n).