Do you think IIT Guwahati certified course can help you in your career?
No
Introduction 🥳
A binary search tree is a tree in which all nodes left to the root node have values less than the root node, and all nodes right to the root node have values greater than the root node. The other difference is all of the subtrees in the binary search tree are themselves a binary search tree.
This blog will discuss a simple DSA problem: Check for identical BSTs without building the trees.
Problem Statement 🧾
The problem "Check for identical BSTs without building the trees" states that you are given two arrays representing some nodes. So we created BSTs from both of these arrays, and now we need to check if the BSTs created from these arrays are identical or not. The complication here is that we cannot create the trees (i.e., we cannot create and then compare them). We need to check if these arrays are identical or not without constructing a tree.
Examples
Example
Input:
Arr1[] = {2, 5, 4, 6, 1}
Arr2[] = {2, 1, 5, 4, 6}
Output: Yes, Arrays are identical
Approach
To check for identical BSTs without building the trees, we will use some basic properties of binary search trees: all elements in the left subtree are smaller than the root node. At the same time, all elements on the right are larger than the root node.
Algorithm
Firstly we will check if the size of both the arrays is different, then BSTs formed can't be identical.
Check if the size of the array is 0, then return true.
If the above two conditions are false, then we will check if the root of both the trees is the same by checking if 'array1[0]' is equal to 'array2[0]'.
If the 3rd condition is true, then we recursively for left and right subtree by doing the following:
Create ‘array_left1’ and ‘array_right1’ using elements of ‘array1’, ‘array_left1’ contain elements of ‘array1’ which are less than root node, and ‘array_right1’ contain elements which are greater than root.
Similarly, for ‘array2’, create ‘array_left2’ and ‘array_right2’ using elements of ‘array2’, ‘array_left2’ contain elements of ‘array2’ which are less than the root node, and ‘array_right2’ contains elements that are greater than root.
Make a recursive call for ‘array_left1’ and ‘array_left2’ to check for the left subtree.
Another recursive call for ‘array_right1’ and ‘array_right2’ for checking the right subtree.
If the result of conditions C and D is true, then return true otherwise, return false.
Example
Let's now discuss working through an example, and then we will code it:
Iteration 1:
Check size of arrays, Size of array1 = 7 = Size of array2
Check root element
Array separation after the first recursion call will be
As shown in the image
array_left1 = [1,0,2]
array_right1 = [5,4,6]
array_left2 = [1,2,0]
array_right2 = [5,4,6]
Iteration 2 :
Call function for array_left1 and array_left2
So now array1 = array_left1 = [1,0,2] and array2 = array_left2 = [1,2,0].
Check size if arrays, Size of array1 = 3 = Size of array2
Check root element
Array separation after the next recursion call for the left subtree will be
As the left subtree is identical for array1 and array2, so left = true.
Iteration 3:
Call function for array_right1 and array_right2
So now array1 = array_right1 = [5,4,6] and array2 = array_right2 = [5,4,6].
Check size if arrays, Size of array1 = 3 = Size of array2
Check root element
Array separation after the next recursion call for the right subtree will be
As the right subtree is identical for array1 and array2, so right = true.
Both right and left are true so return true to the main function call.
Implementation in C++
// A C++ program = check for identical BSTs without building the trees
#include<bits/stdc++.h>
using namespace std;
bool checkBST(vector<int>arr1, vector<int>arr2)
{
// Calculate size of both arrays
int n = arr1.size();
int m = arr2.size();
// Check if size is different
if(n != m)
return false;
// Check if size is zero
if(n == 0)
return true;
// Check for root node
if(arr1[0] == arr2[0])
{
vector<int>array_left1;
vector<int>array_right1;
vector<int>array_left2;
vector<int>array_right2;
for(int i=1;i<n;i++)
{
// Adding elements in left subtree of arr1
if(arr1[i] < arr1[0])
array_left1.push_back(arr1[i]);
// Adding elements in left subtree of arr1
else
array_right1.push_back(arr1[i]);
// Adding elements in left subtree of arr2
if(arr2[i] < arr2[0])
array_left2.push_back(arr2[i]);
// Adding elements in left subtree of arr2
else
array_right2.push_back(arr2[i]);
}
bool left = checkBST(array_left1, array_left2);
bool right = checkBST(array_right1, array_right2);
return left && right;
}
// If all conditions are false then return false
return false;
}
int main()
{
// Declaring two arrays
vector<int>arr1;
vector<int>arr2;
// Calculate the size of both arrays
int n,m;
cout<<"Enter size of arrays : ";
cin>>n>>m;
cout<<"Enter elements of array 1 - ";
for(int i=0;i<n;i++)
{
int x;
cin>>x;
arr1.push_back(x);
}
cout<<"Enter elements of array 2 - ";
for(int i=0;i<m;i++)
{
int x;
cin>>x;
arr2.push_back(x);
}
// Check is size of arrays is different
if(n != m)
{
cout << "No, Arrays are not identical";
exit(0);
}
if(checkBST(arr1, arr2))
cout << "Yes, Arrays are identical";
else
cout << "No, Arrays are not identical";
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity of the problem “Check for identical BSTs without building the trees” using the above approach is O(N), for traversing both arrays, where N is the number of elements in the array.
Space Complexity 🚀
The space complexity of the problem “Check for identical BSTs without building the trees” using the above approach is O(N) for two arrays of size N. Check out this problem - Largest BST In Binary Tree
Frequently Asked Questions
What is a binary tree?
A binary tree is a data structure having a maximum of two children. There can only be two children per element in a binary tree; hence we usually refer to them as the left and right children.
What is a binary search tree?
A binary search tree is a binary tree in which all of the nodes left to the root node have values less than the root node, and all of the nodes right to the root node have values greater than the root node.
What is a Full Binary Tree?
A full binary tree is a particular kind of binary tree in which every parent node and internal node either has two children or none at all.
Why is Binary Search Tree used?
It is beneficial in many scenarios where we have to compare the sorted data then it can be used.
Which property of BST is used to check for identical BSTs without building the trees?
The property of binary search trees is that all elements in the left subtree are smaller than the root. While all elements on the right of the root are larger than the root is used for solving this problem.
Conclusion
In this article, we have discussed a coding problem in which we have to Check for identical BSTs without building the trees. We have seen the question's solution, time, and space complexity(Check for identical BSTs without building the trees).
If you found this blog has helped you enhance your knowledge about the above question, and if you want to learn more, check out our articles