530. Minimum Absolute Difference in BST Easy

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.

Example 1:
Input: root = [4,2,6,1,3]
Output: 1

Example 2:
Input: root = [1,0,48,null,null,12,49]
Output: 1

Approach

Input: The root node of a binary search tree root

Output: Return the minimum absolute difference between any two different node values.

This problem is a Binary Search Tree Traversal + Inorder Traversal problem.

According to the characteristics of a binary search tree, we can use inorder traversal to get an ascending order.

In this ascending order, we can compare the difference between adjacent nodes step by step, and record the minimum value to get the answer.

Implementation

python

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        prev = None  # Record the previously visited node (the previous node in inorder traversal)
        ans = float('inf')  # Initialize the minimum difference to infinity

        # Inorder traversal, taking advantage of the ordering of BST
        def dfs(node):
            nonlocal ans, prev
            if not node:
                return
            
            # Traverse left subtree
            dfs(node.left)

            # Update the minimum difference using the current node and the previous node's values
            if prev is not None:
                ans = min(ans, node.val - prev.val)
            prev = node  # Update previous node

            # Traverse right subtree
            dfs(node.right)

        dfs(root)
        return ans

javascript

/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    let ans = Infinity;
    let prev = null;

    function dfs(node) {
        if (!node) return;

        dfs(node.left)
        if (prev != null)
            ans = Math.min(ans, node.val - prev.val)
        prev = node

        dfs(node.right)
    }

    dfs(root);
    return ans;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

Links

530. Minimum Absolute Difference in BST (English)

530. 二叉搜索树的最小绝对差 (Chinese)