Find the minimum absolute difference in two different BST

Urwashi Priya
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss a binary search tree problem asked frequently in Interviews.

A common prerequisite for any BST problem is the knowledge of recursion because, without conceptually understanding recursion, things can become difficult for us to understand. Now, before we proceed, we must know what a Binary Search Tree is?

A Binary Search Tree is a binary tree that follows a particular property that any node in the left subtree in the binary search tree is smaller than the root node, and any node in the right subtree in the binary search tree is greater than the root node. Every subtree of the binary search tree must follow this property,

 Let’s look at the problem first.

Our problem is to Find the minimum absolute difference in two different BST’s.

We are given two binary search trees, and we need to find the minimum absolute difference possible in two different BST by selecting two nodes at a time from both the trees. 

Example: Say 2 BSTs are:

 

 

So, the minimum difference possible here would be 8-8=0.

Brute-force Approach

We can approach how to Find the minimum absolute difference in two different BST in a very basic way using two arrays.

 

Define a function to move to the next element of binary search trees. 

For every node in the first BST, traverse every node in the second BST.

Keep calculating the difference.

Find the minimum difference.

 

If BST1 consist of n nodes and BST2 consist of m nodes,

Then time complexity = O(n*m).

 

Optimised Approach

We can approach how to Find the minimum absolute difference in two different BST in an optimised way using a two-pointer approach.

 

Define a function to move to the next element of binary search trees. This makes use of the concept of the stack. 

Then we define a function to find the minimum difference possible.

  • We first declare two iterators.
  • We then define both iterators one by one. One iterator is used to traverse the first BST, and the second iterator is used to traverse the second BST.
  • Then we use two pointer technique to find differences with data present in the iterators and store it in a variable, say the answer. We keep on doing this step till we find the minimum possible difference.
  • If the value of the first iterator is less than the value of the second iterator, then we move to the next element of the first BST else move to the next element of the second BST

Time Complexity = n + m

n: no of elements in the first binary search tree.

m: no of elements in the second binary search tree.

Space complexity: O(h1+h2).

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

If you can’t solve, don’t be sad. This is a part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm()

___________________________________________________________________

Procedure minDiff(node* root1, node* root2):

___________________________________________________________________

1.   Define next function first to move to the next element of binary search trees.

2.   stack<node *> it1, it2;

3.   node* curr = root1;

      while (curr != NULL)

        it1.push(curr), curr = curr->left;

4.   curr = root2;

      while (curr != NULL)

        it2.push(curr), curr = curr->left;

5.   int ans = INT_MAX;

6.   while (it1.size() and it2.size())

int v1 = it1.top()->data;

           int v2 = it2.top()->data;

           ans = min(abs(v1 - v2), ans);

if (v1 < v2)

            next(it1);

           else

            next(it2);

     return ans;

end procedure

___________________________________________________________________

CODE IN C++

//Find the minimum absolute difference in two different BST
#include <bits/stdc++.h>
using namespace std;
 
// structure of Binary tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
// Function to move to the next element of Binary Search Tree
void next(stack<node*>& it)
{
 
    node* curr = it.top()->right;
    it.pop();
    while (curr != NULL)
        it.push(curr), curr = curr->left;
}
 
// Function to find minimum difference possible
int minDiff(node* root1, node* root2)
{
 
    // Iterator for two Binary Search Trees
    stack<node *> it1, it2;
 
    // Initializing both iterator
    node* curr = root1;
    while (curr != NULL)
        it1.push(curr), curr = curr->left;
 
    
    curr = root2;
    while (curr != NULL)
        it2.push(curr), curr = curr->left;
 
    // final answer
    int ans = INT_MAX;
 
    // Using Two pointer approach
    while (it1.size() and it2.size()) {
 
        
        int v1 = it1.top()->data;
        int v2 = it2.top()->data;
 
        // Updating final answer
        ans = min(abs(v1 - v2), ans);
 
        // Case when v1 < v2
        if (v1 < v2)
            next(it1);
        else
            next(it2);
    }
 
   
    return ans;
}
 
// Driver code
int main()
{
    // first binary search tree
 
    node* root2 = new node(5);
    root2->left = new node(3);
    root2->right = new node(7);
    root2->left->left = new node(2);
    root2->left->right = new node(4);
    root2->right->left = new node(6);
    root2->right->right = new node(8);
 
    // second binary search tree
    node* root1 = new node(10);
    root1->left = new node(6);
    root1->right = new node(15);
    root1->left->left = new node(3);
    root1->left->right = new node(8);
    root1->right->left = new node(11);
    root1->right->right = new node(18);
 
    cout << minDiff(root1, root2);
 
    return 0;
}

 

Output

Sample Input: 
5 3 7 2 4 6 8
10 6 15 3 8 11 18

Sample Output:
0

Complexity Analysis

Time Complexity: O(n+m).

Analysing Time Complexity:

No of elements in the first binary tree = n.

No of elements in the second binary tree = m.

Therefore, n+m time is taken

Space complexity: O(h1+h2).

Height of first binary tree = h1.

Height of second binary tree = h2.

Frequently Asked Questions

  1. What are the prerequisites for the binary search tree problem?
    Answer) We must have a detailed understanding of recursion.
    To know more about recursion, click here.
     
  2. What are the steps to follow in such kind of question? 
    Answer)step 1: find one or more base cases.
    Step 2: Call the same function for the left subtree.
    Step 3: Call the same function for the right subtree.
    Step 4: Join results and then evaluate what is asked for.
    Follow split and combine approaches.
     
  3. What is the difference between a binary tree and a binary search tree?
    Answer) A binary tree is a non-linear or unordered data structure consisting of 0,1 or 2 nodes. A binary search tree is an ordered or organised data structure arranged in a specific given order, i.e. left subree<root<right subtree. 

Key Takeaways

This article taught us how to Find the minimum absolute difference in two different BSTs. We discussed its implementation using illustrations, pseudocode, and proper code.

We hope you could take away the critical techniques like analysing problems by walking over the execution of the examples and figuring out the recursive pattern, i.e. followed in most binary search tree problems.

Now, we recommend you practice problems based on BST to master your fundamentals. You can get a range of questions similar to this on CodeStudio

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think