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

``````
``````