Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Brute-force Approach
3.
Optimised Approach
3.1.
PseudoCode
3.2.
CODE IN C++
3.2.1.
Complexity Analysis
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Find the minimum absolute difference in two different BST

Urwashi Priya
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## 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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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;

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.

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.

Check out this problem - Longest Subarray With Sum K

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

Live masterclass