How do you solve Minimum Absolute Difference in BST on LeetCode?

Minimum Absolute Difference in BST (LeetCode #530) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: In a BST, in-order traversal yields sorted values, making it easier to find minimum differences.

What is the brute force solution for Minimum Absolute Difference in BST?

The brute force approach for Minimum Absolute Difference in BST is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves comparing every pair of nodes in the BST to find the minimum absolute difference. This is straightforward but inefficient, especially for larger trees. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Minimum Absolute Difference in BST?

Always consider the properties of the data structure you are working with — they can lead to more efficient solutions. Explain your thought process clearly as you work through the problem; it shows your understanding. Practice writing clean and efficient code, as readability is important in interviews.

What are common mistakes when solving Minimum Absolute Difference in BST?

Not realizing that the minimum difference can only occur between adjacent values in a sorted list. Overlooking the properties of BSTs which can simplify the problem.

#530

Minimum Absolute Difference in BST

Easy

TreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary TreeIn-order TraversalTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal solution leverages the properties of a BST and performs an in-order traversal to find the minimum absolute difference in a single pass. This is efficient because the in-order traversal produces a sorted list of values.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to keep track of the previous node's value and the minimum difference.
2Step 2: Perform an in-order traversal of the BST, updating the minimum difference whenever a new node is visited.
3Step 3: Return the minimum difference found.

solution.py21 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def getMinimumDifference(self, root: TreeNode) -> int:
10        self.prev = None
11        self.min_diff = float('inf')
12        self.inorder_traversal(root)
13        return self.min_diff
14
15    def inorder_traversal(self, node):
16        if node:
17            self.inorder_traversal(node.left)
18            if self.prev is not None:
19                self.min_diff = min(self.min_diff, abs(node.val - self.prev))
20            self.prev = node.val
21            self.inorder_traversal(node.right)

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once during the in-order traversal. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

1In a BST, in-order traversal yields sorted values, making it easier to find minimum differences.
2The minimum absolute difference will always be between adjacent nodes in the sorted order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.