Minimum Absolute Difference in a BST-Interview Problem

Minimum Absolute Difference in a BST- Interview Problem

Difficulty: Easy

Asked in: Google

Understanding the Problem:

Given a BST(Binary Search Tree) with non-negative values, write a program to find the minimum absolute difference between values of any two nodes. Your answer should be the minimum difference possible taking any pair of nodes into account.

Possible questions to ask the interviewer:

What if the given tree is empty or has only one node? ( Ans: The given tree will have at-least two nodes.)

For Example: →

Input: Given Binary Search Tree

                  7
                /   \
               3     10
              / \    / \
             2   5  8   12

Output: 1

Explanation: The minimum absolute difference between any pair of nodes in this tree is 1, which is the difference between the nodes (3,2) and (8,7).

Input: Given Binary Search Tree

                   10
                  /   \
                 7     16
                /  \   / \
               5    8 12  20

Output: 2

Explanation: Here, the minimum absolute difference possible between any two pair is 2 from nodes (10,8).

Before we discuss the solution, you may want to give it a try. Try this problem here .

Solution

Solution idea

The idea of the solution is to use inorder traversal of the binary search tree. As you must already know, inorder traversal of a binary search tree gives us the elements in sorted order.

Once we have the elements in sorted order, we can find the minimum absolute difference by comparing adjacent elements of the list and finding the difference.

Solution steps

We will traverse the given tree using inorder traversal.
We will store the elements while traversing into a list.
We will initialize a variable min_abs_diff with the maximum value of integer possible.
We will compare the adjacent values of the elements in the list and find the difference. If the difference is smaller than the value stored in the min_abs_diff , we will update the value.
We will keep doing this until we reach the end of the array. At last, we will get the minimum absolute difference possible in our variable min_abs_diff .

Pseudo-code

void inorder(TreeNode root, int[] A)   
    {
        if(root == NULL)
            return;
        inorder(root->left, A)
        A.add(root->val)            //adding elements 
        inorder(root->right, A)
    }
    int getMinimumAbsDiff(TreeNode root) {
        int [] arr
        int min_so_far = INT_MAX // max int value possible
        inorder(root, A)
        for(int i=0 to A.length -1 ; i=i+1)
        {
            if ((A[i+1] - A[i]) < min_so_far)
                min_so_far = A[i+1] - A[i]
        }
        return min_so_far
    }

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N) (Why?)

Critical ideas to think!

Think of an approach where we compare each node with it’s right and left nodes only and find the difference between them only. Then find the minimum difference between those differences. What is the problem with this approach? In what kind of situation this approach will fail?