# 530. Minimum Absolute Difference in BST
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
Input:
1
\
3
/
2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
# Solution
Approach 1: a BST means an inorder traversal is sorted. Iterative procedure.
Approach 2: a BST means an inorder traversal is sorted. Recursive procedure: we can either keep "global variables" (nonlocal variables in python) for the previous value and the result, or have the recursive precedure return the result bounded by parameters.
# Code (Python)
Approach 1:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# iterative -- a BST means an inorder traversal is sorted
result = float('inf')
prev_val = -float('inf')
node = root
stack = []
while node:
stack.append(node)
node = node.left
while stack:
node = stack.pop()
result = min(result, node.val - prev_val)
prev_val = node.val
node = node.right
while node:
stack.append(node)
node = node.left
return result
Approach 2:
def getMinimumDifference(self, root):
# recursive -- inorder traversal
prev = -float('inf')
min_diff = float('inf')
def inorder(node):
if not node:
return
# nonlocal is python 3's way of asking vars to bind to an outer (but not global) scope if reassigned
nonlocal prev
nonlocal min_diff
inorder(node.left)
min_diff = min(min_diff, node.val - prev)
prev = node.val
inorder(node.right)
inorder(root)
return min_diff
def getMinimumDifference(self, root):
# recursive -- each node is bounded by a lower and upper bound (the values immediately smaller and bigger than itself), and those can be set with recursive calls
def get_min_diff(node, lo_bound, hi_bound):
if not node:
return float('inf')
return min(
node.val - lo_bound,
hi_bound - node.val,
get_min_diff(node.left, lo_bound, node.val),
get_min_diff(node.right, node.val, hi_bound)
)
return get_min_diff(root, -float('inf'), float('inf'))
# Code (C++)
Approach 1:
Approach 2: