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;
}
You can also try this code with Online C++ Compiler
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
-
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.
-
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.
-
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.
245+ registered 
