# 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: