Solution Explanation: Minimum Absolute Difference in BST

This problem asks for the minimum absolute difference between any two nodes in a Binary Search Tree (BST). The key insight is leveraging the inherent property of a BST: an inorder traversal yields a sorted sequence of node values. Therefore, the minimum difference will always exist between two adjacent nodes in this sorted sequence.

Approach: Inorder Traversal

The solution employs an inorder traversal of the BST. Inorder traversal visits nodes in the order: left subtree, root, right subtree. Because it's a BST, this order guarantees the visited nodes are in ascending order. We track the previously visited node's value (pre) and calculate the absolute difference between the current node's value and pre. The minimum of these differences is the final answer.

Algorithm:

1. Initialization:

   • pre: Stores the value of the previously visited node. Initialized to negative infinity (-inf) to handle the first node.
   • ans: Stores the minimum absolute difference found so far. Initialized to positive infinity (inf).

2. Recursive Inorder Traversal (dfs function):

   • Base Case: If the current node is null, return.
   • Recursive Step (Left Subtree): Recursively traverse the left subtree.
   • Current Node Processing:
     • Update ans with the minimum of ans and the absolute difference between the current node's value and pre.
     • Update pre to the current node's value.
   • Recursive Step (Right Subtree): Recursively traverse the right subtree.

3. Return ans: After the traversal completes, ans holds the minimum absolute difference.

Time and Space Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the BST. This is because we perform a single inorder traversal, visiting each node exactly once.

• Space Complexity: O(H), where H is the height of the BST. This is due to the recursive call stack used during the inorder traversal. In the worst case (a skewed BST), H could be N, resulting in O(N) space complexity. In the best case (a balanced BST), H is log₂(N), resulting in O(log N) space complexity.

Code Examples (Python and Java):

Python:

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        pre = float('-inf')
        ans = float('inf')
 
        def dfs(node):
            nonlocal pre, ans
            if not node:
                return
            dfs(node.left)
            ans = min(ans, node.val - pre)
            pre = node.val
            dfs(node.right)
 
        dfs(root)
        return ans

Java:

class Solution {
    private int pre = Integer.MIN_VALUE;
    private int ans = Integer.MAX_VALUE;
 
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return ans;
    }
 
    private void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        ans = Math.min(ans, node.val - pre);
        pre = node.val;
        dfs(node.right);
    }
}

The code in other languages (C++, Go, TypeScript, Rust, JavaScript) follows a similar structure, adapting the syntax and data types to the respective languages. The core algorithm remains consistent across all implementations.