02(April) Minimum Absolute Difference In BST

02. Minimum Absolute Difference in BST

The problem can be found at the following link: Question Link

Problem Description

Given a binary search tree having ( n ) (( n > 1 )) nodes, the task is to find the minimum absolute difference between any two nodes.

Example:

Input Tree:

Image

Output:

10

Explanation: There are no two nodes whose absolute difference is smaller than 10.

My Approach

1. Inorder Traversal:

   • Traverse the BST in inorder traversal, which will give the elements in sorted order.

   • Keep track of the previous visited node's value and compute the absolute difference between the current node's value and the previous node's value.

   • Update the minimum absolute difference encountered so far.

2. Return:

   • Return the minimum absolute difference.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n), as we traverse through all the nodes of the BST once during the inorder traversal.

• Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space for storing variables like prev and minDiff.

Code (C++)

class Solution
{
public:
    void inorder(Node *root, int &prev, int &minDiff) {
        if (!root) return;
        inorder(root->left, prev, minDiff);
        if (prev != INT_MAX) {
            minDiff = min(minDiff, root->data - prev);
        }
        prev = root->data;
        inorder(root->right, prev, minDiff);
    }

    int absolute_diff(Node *root) {
        int minDiff = INT_MAX;
        int prev = INT_MAX;
        inorder(root, prev, minDiff);
        return minDiff;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count