LeetCode 530 -Minimum Absolute Difference in BST - ( Tutorial + C Code )

=>Try Yourself First. For help Scroll Down.

Problem link: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

Problem clearance: You will be given a binary search tree. You need to find the minimum absolute difference between any two node values. 

Tutorial: 

Binary Search Tree: Binary search tree (BST) is a binary tree whose root value will always be greater than its left subtree and will always be lesser than its right subtree. See the image below - 

Courtesy: GeeksForGeeks [ Edited ]

If you consider the root node A, you can see the value of A is greater than the value of left node B and lesser than the value of right node C. Now if you go to the left subtree of root A you can see the value of root node B of the left subtree is greater than the value of left node D and lesser than the value of right node E. If you traverse continuously you can find the properties among other nodes. [ Tip: It will be better for you if you write things in a notebook and see how it works.]

Minimum absolute difference: If we consider the difference of the value of any two nodes we will have  ^(N*(N-1))⁄₂  total values. Some of them negative maybe. As we are said to take absolute of all those values we will neglect the negative sign. What we will concern is about the value. So if the value is -10 then we will consider it as 10. Now if we take a minimum of all those values then we will have a minimum absolute difference. 

Approach: 

1. The simplest approach is to traverse all the nodes of the given tree. Store the values in an array and then calculate the absolute difference between each of the values and take the minimum of those values we will have the answer. But see the constraints. We may have 10⁴ nodes in the given tree. So traversing all of the N nodes will cost O(N) complexity. And then comparing all those nodes will cost O(N²) complexity which is approximately 10⁸ operations roughly, maybe more than that.

2. But we can optimize the previous approach if we traverse cleverly to have the values sorted. Then we do not need O(N²) complexity. We can reduce the comparison operation to O(N) complexity. Instead of traversing and storing values randomly let us just do inorder traversal. For the BST properties, if we will have the array sorted. I will share the reason some other day in another article. Now we have stored the array value in a sorted way. Now just find the absolute difference between two adjacent values of the array. And take the minimum. You will have the answer. The overall complexity is O(N) as we are just traversing the nodes. 

Hope you solved it by now. You can have a look at the implementation if you stuck somewhere.

Code: 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int min(int a, int b){
    if(a > b ) return b;
    return a;
}

int abs(int x){
    if(x<0) x = -x;
    return x;
}

int arr[100005];
int idx = 0;

void crawl(struct TreeNode * root){
    if(root == NULL) return;
    if(root->left) crawl(root->left);
    arr[++idx] = root->val;
    if(root->right) crawl(root->right);
}

int getMinimumDifference(struct TreeNode* root){
    idx = 0;
    crawl(root);
    int ans = 987654321;
    for(int i=2; i<=idx; i++){
        printf("%d %d %d\n", arr[i], arr[i-1], abs(arr[i] - arr[i-1]));
        ans = min(ans, abs(arr[i] - arr[i-1]));
    }
    return ans;
}

=>Leave a comment for any kinds of Hugs and/or Bugs. Thank you.