Minimum Absolute Difference in BST

Question

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

Note: There are at least two nodes in this BST.

Tags

• Binary Search Tree
• In-order Traversal

Thought

In order to find the minimum absolute difference, it is necessary to traversal the tree from the smallest to the largest, which is the in-order traversal.

The basic approach for in-order traversal through recursion is below:

1. traversal(current_node.left)
2. Do your stuff with current_node
3. traversal(current_node.right)

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    maxValue = -float('inf')
    minDiff = float('inf')

    def helper(self, node):
        if not node:
            return
        self.helper(node.left)
        self.minDiff = min(self.minDiff, node.val - self.maxValue)
        self.maxValue = node.val
        self.helper(node.right)

    def getMinimumDifference(self, root):
        """
        traversal of BST
        :type root: TreeNode
        :rtype: int
        """
        self.helper(root)
        return self.minDiff