# LeetCode 530: Minimum Absolute Difference in BST ## Problem Restatement We are given the root of a Binary Search Tree. We need to return the minimum absolute difference between the values of any two different nodes in the tree. The important property is that the tree is a BST. For every node: ```python left subtree values < node value < right subtree values ``` Because of this property, an inorder traversal visits the node values in sorted order. The problem guarantees that the tree has at least two nodes. The node values are non-negative. ## Input and Output | Item | Meaning | |---|---| | Input | The root of a Binary Search Tree | | Output | The minimum absolute difference between any two node values | | Node count | At least `2` nodes | | Node values | Non-negative integers | Function shape: ```python def getMinimumDifference(root: Optional[TreeNode]) -> int: ... ``` ## Examples Consider this BST: ```text 4 / \ 2 6 / \ 1 3 ``` The inorder traversal gives: ```python [1, 2, 3, 4, 6] ``` Now compare adjacent values: ```python 2 - 1 = 1 3 - 2 = 1 4 - 3 = 1 6 - 4 = 2 ``` The minimum difference is: ```python 1 ``` So the answer is: ```python 1 ``` Another example: ```text 1 \ 48 / \ 12 49 ``` The inorder traversal gives: ```python [1, 12, 48, 49] ``` Adjacent differences are: ```python 12 - 1 = 11 48 - 12 = 36 49 - 48 = 1 ``` The minimum difference is: ```python 1 ``` ## First Thought: Compare Every Pair A direct solution is to collect all node values, then compare every pair. For each pair of values `a` and `b`, compute: ```python abs(a - b) ``` Then keep the smallest value. This works, but it ignores the BST property. If there are `n` nodes, comparing every pair takes: ```python O(n^2) ``` We can do better. ## Key Insight In a sorted list, the minimum absolute difference must appear between two adjacent elements. For example: ```python [1, 2, 3, 4, 6] ``` The closest pair cannot be `1` and `4`, because values between them, such as `2` and `3`, are even closer candidates. So after sorting, we only need to compare neighbors. A BST gives sorted values for free through inorder traversal: ```python left -> node -> right ``` Therefore, we can traverse the BST in inorder order and compare each node value with the previously visited value. ## Algorithm Use inorder traversal. Maintain two variables: ```python prev answer ``` `prev` stores the value of the previously visited node in inorder order. `answer` stores the smallest difference seen so far. During traversal: 1. Visit the left subtree. 2. Process the current node. 3. Compare `node.val` with `prev`, if `prev` exists. 4. Update `answer`. 5. Set `prev = node.val`. 6. Visit the right subtree. At the end, return `answer`. ## Correctness Inorder traversal of a BST visits values in increasing order. So the traversal produces the same order as sorting all node values. In any sorted sequence, the minimum absolute difference between two values occurs between adjacent values. If two values are not adjacent, then at least one value lies between them, and one of the smaller gaps around that middle value is no larger than the larger outer gap. The algorithm compares each value with the value immediately before it in inorder order. Therefore, it checks every adjacent pair in the sorted sequence. Since the minimum difference must be among these adjacent pairs, the algorithm finds the correct minimum absolute difference. ## Complexity Let `n` be the number of nodes and `h` be the height of the tree. | Metric | Value | Why | |---|---:|---| | Time | `O(n)` | Each node is visited once | | Space | `O(h)` | Recursion stack height is the tree height | In the worst case, a skewed tree has height `n`, so the space can be `O(n)`. For a balanced tree, the space is `O(log n)`. ## Implementation ```python # 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 from typing import Optional class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) -> int: prev = None answer = float("inf") def inorder(node: Optional[TreeNode]) -> None: nonlocal prev, answer if node is None: return inorder(node.left) if prev is not None: answer = min(answer, node.val - prev) prev = node.val inorder(node.right) inorder(root) return answer ``` ## Code Explanation We initialize: ```python prev = None answer = float("inf") ``` `prev` starts as `None` because there is no previous node before the first node in inorder traversal. `answer` starts as infinity so that the first valid difference will replace it. The traversal function is: ```python def inorder(node: Optional[TreeNode]) -> None: ``` If the node is missing, we stop: ```python if node is None: return ``` Then we visit the left subtree: ```python inorder(node.left) ``` At this point, all smaller values have already been processed. Now we process the current node. If there is a previous value, we compare: ```python answer = min(answer, node.val - prev) ``` We do not need `abs` here because inorder traversal gives increasing values, so `node.val >= prev`. Then we update: ```python prev = node.val ``` Finally, we visit the right subtree: ```python inorder(node.right) ``` This continues the sorted traversal. ## Iterative Version The same idea can be implemented with an explicit stack. ```python from typing import Optional class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) -> int: stack = [] node = root prev = None answer = float("inf") while stack or node: while node: stack.append(node) node = node.left node = stack.pop() if prev is not None: answer = min(answer, node.val - prev) prev = node.val node = node.right return answer ``` This avoids recursive function calls, but the logic is the same. ## Testing ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def run_tests(): s = Solution() root = TreeNode( 4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6), ) assert s.getMinimumDifference(root) == 1 root = TreeNode( 1, None, TreeNode(48, TreeNode(12), TreeNode(49)), ) assert s.getMinimumDifference(root) == 1 root = TreeNode(2, TreeNode(1), None) assert s.getMinimumDifference(root) == 1 root = TreeNode(10, TreeNode(5), TreeNode(20)) assert s.getMinimumDifference(root) == 5 print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `[4,2,6,1,3]` | Standard balanced-ish BST example | | `[1,null,48,null,null,12,49]` | Checks a right-heavy shape | | Two nodes | Minimum valid tree size | | Wider gap values | Confirms the minimum is computed from sorted neighbors |