# 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.
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).
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)
# 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
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++)