Minimum Absolute Difference in BST

Problem Id: 530 Difficulty: Easy Tag: Tree


Intuition

The minimum absolute difference of any 2 nodes in a BST must be one of the differences between 2 continuous nodes in order.

So we could use inorder traversal to visit nodes in order and calculate the difference between any 2 continuous nodes to solve this problem.

Solution


# 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: TreeNode) -> int:
        self.last = None
        self.min_diff = float('inf')
        self._inorder(root)
        return self.min_diff

    def _inorder(self, node):
        if node is None:
            return
        self._inorder(node.left)

        # visit this node
        if self.last is None:
            self.last = node.val
        else:
            self.min_diff = min(node.val - self.last, self.min_diff)
            self.last = node.val

        self._inorder(node.right)