530. Minimum Absolute Difference in BST

• categories: Code, Interview Question, leetcode, Easy
• source: https://leetcode.com/problems/minimum-absolute-difference-in-bst
• topics: Tree, DFS

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Idea

inorder traversal handles the nodes in sorted order, traverse and compare with previous using inorder BFS

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        minDistance = float(inf)
        prevNode = None
 
        def inorder(node):
            nonlocal minDistance, prevNode
            if node is None:
                return
            inorder(node.left)
            # Find the difference with the previous value if it is there.
            if prevNode is not None:
                minDistance = min(minDistance, node.val - prevNode)
            prevNode = node.val
            inorder(node.right)
 
        inorder(root)
        return minDistance