
    class Solution {
        public int getMinimumDifference(TreeNode root) {
            List values = new ArrayList<>();
            inOrder(root, values);
            
            int minDiff = Integer.MAX_VALUE;
            for (int i = 1; i < values.size(); i++) {
                minDiff = Math.min(minDiff, values.get(i) - values.get(i - 1));
            }
            return minDiff;
        }
        private void inOrder(TreeNode node, List values) {
            if (node == null) return;
            inOrder(node.left, values);
            values.add(node.val);
            inOrder(node.right, values);
        }
    }

Time Complexity: O(n) and Space Complexity: O(n)

The "Minimum Absolute Difference in BST" problem involves finding the smallest absolute difference between values of any two nodes in a Binary Search Tree (BST). Since a BST has a property that for every node, all values in the left subtree are smaller and all values in the right subtree are larger, this property helps in efficiently calculating the minimum absolute difference between any two nodes.

The problem can be solved by exploiting the in-order traversal of the BST. This traversal visits the nodes in sorted order, which allows us to compute the difference between consecutive nodes efficiently.

Problem Statement

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

The tree node structure is defined as above. The goal is to find and return the smallest absolute difference between the values of any two nodes in the BST.

Approach

The key observation here is that the smallest absolute difference will be between two consecutive nodes in an in-order traversal of the BST. This is because in a BST, the nodes are visited in ascending order during an in-order traversal.

Perform an in-order traversal of the BST.
As we traverse, keep track of the previously visited node and calculate the absolute difference between the current node and the previously visited node.
Return the minimum difference after completing the traversal.

This approach ensures that we only visit each node once and efficiently compute the minimum absolute difference by leveraging the in-order traversal of the BST.

Algorithm

The algorithm follows these steps:

Initialize a variable to store the minimum difference (initially set to infinity).
Perform an in-order traversal of the BST, visiting nodes in ascending order.
Update the minimum difference whenever a smaller difference is found.
Return the minimum difference after completing the traversal.

By using this method, we efficiently compute the minimum absolute difference between nodes in the BST with a time complexity of O(n), where n is the number of nodes in the tree.

Example

Consider the following Binary Search Tree:

Performing an in-order traversal of this tree gives the following node values: [1, 2, 3, 4, 5, 6, 7]. The absolute differences between consecutive nodes are:

            |2 - 1| = 1
            |3 - 2| = 1
            |4 - 3| = 1
            |5 - 4| = 1
            |6 - 5| = 1
            |7 - 6| = 1

The minimum absolute difference between any two nodes is 1.

Code Implementation

Below is the Python implementation of the algorithm to find the minimum absolute difference in the BST:

In this code: - The `getMinimumDifference` function initializes the `prev` node as None and the `min_diff` variable to infinity. - The helper function `inorder` is defined to perform the in-order traversal of the tree. During the traversal, the absolute difference between the current node’s value and the previously visited node’s value is computed, and the minimum difference is updated accordingly. - After the traversal, the function returns the minimum absolute difference found.

Time Complexity

The time complexity of the solution is O(n), where n is the number of nodes in the Binary Search Tree. This is because we perform a single in-order traversal of the tree, visiting each node exactly once.

The space complexity is O(h), where h is the height of the tree, due to the recursion stack used during the in-order traversal. In the worst case (unbalanced tree), the height can be O(n), but in the best case (balanced tree), the height is O(log n).

Optimized Approach

The current solution is already optimized for the problem. The in-order traversal ensures that we only visit relevant nodes, and we calculate the minimum absolute difference efficiently. For a balanced tree, the space complexity is minimal (O(log n)), and the time complexity is linear in terms of the number of nodes.

There is no significant optimization that can further improve the time complexity, as we need to visit each node at least once to compute the absolute differences.

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the tree, as we need to traverse the entire tree to compute the differences.

The space complexity remains O(h), where h is the height of the tree. In the worst case, the space complexity is O(n) for an unbalanced tree, and in the best case, it is O(log n) for a balanced tree.

Conclusion

The "Minimum Absolute Difference in BST" problem efficiently finds the smallest difference between any two nodes in a Binary Search Tree by leveraging the properties of the tree and performing an in-order traversal. The time complexity of the solution is O(n), and the space complexity is O(h), where h is the height of the tree. This approach is optimal for most use cases and ensures that we can compute the result in a time-efficient manner.