In this article, we’ll be looking at the problem named Check if two BSTs contain the same set of elements or not. We will solve this problem with the help of tree concepts like inorder traversal. We will also discuss the step-wise algorithm and the time and space complexity.
Problem Statement 🖥️
There are two Binary Search Trees consisting of unique positive elements, and we have to check whether the two BSTs contain the same set of elements or not.
Example:
Both trees contains the same elements.
OUTPUT:
YES
Explanation 📇
1) Two same Binary Search Tree(BSTs)
In the image, since two BSTs are exactly the same, thus they have to have the same set of elements.
2) Two different BST but having the same set of elements
In the image, two BSTs are not exactly the same, they have the same set of elements which is [3,5,6,7,10,13]
3) Two BSTs not have the same set of elements
The BSTs don't have the same set of elements as the first one has the set [3,5,6,7,10,13] and the second has set [2,5,6,7,11,13]
Traverse the first tree and store its element in a list or array.
Traverse another tree and check whether the current element is present in the list.
If yes, mark the element in the list as negative and search for more elements.
If no, then terminate the traversal and print No.
If all the elements of the 2nd tree are present in the list and marked negative, traverse the list to check if any non-negative elements are left.
If yes, then the first tree has an extra element; else, both trees have the same set of elements.
In this Maximum distance between two occurrences of the same element in the array problem, a simple and brute force approach will be to run two loops and find the first and last occurrence of an element one by one. This approach will take O(n^2) time.
📍Time Complexity: O( n * n ), where n belongs to a number of nodes in the BST.
In this approach for checking two BSTs contain the same set of elements or not, we will use an unordered set to store the value of the tree. We will traverse the trees and store the values in two different sets. In the end, we will compare both sets.
Algorithm 🌐
Define two unordered sets.
Insert the value of 1st tree in set 1 and 2nd tree in set2.
/* Program for BSTs contain the same set of elements or not.*/
#include<bits/stdc++.h>
using namespace std;
/* definition of tree Node */
struct Tree_Node
{
int data;
struct Tree_Node* left;
struct Tree_Node* right;
Tree_Node(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
/* insertion of tree in set */
void insertToSet(Tree_Node* root, unordered_set<int> &s)
{
if (!root)
return;
insertToSet(root->left, s);
s.insert(root->data);
insertToSet(root->right, s);
}
/* checking the values of tree */
bool CheckTwoBSTs(Tree_Node* tree1_root, Tree_Node* tree2_root)
{
if ((!tree1_root && tree2_root) || (tree1_root && !tree2_root))
return false;
if (!tree1_root && !tree2_root)
return true;
unordered_set<int> s1, s2;
insertToSet(tree1_root, s1);
insertToSet(tree2_root, s2);
if(s1 == s2)
return true;
else
return false;
}
/* main function */
int main()
{
/* First Binary tree*/
Tree_Node* tree1_root = new Tree_Node(5);
tree1_root->left = new Tree_Node(3);
tree1_root->right = new Tree_Node(7);
tree1_root->left->left = new Tree_Node(6);
tree1_root->left->right = new Tree_Node(13);
tree1_root->right->right = new Tree_Node(10);
/* Second Binary tree*/
Tree_Node* tree2_root = new Tree_Node(3);
tree2_root->left = new Tree_Node(5);
tree2_root->right = new Tree_Node(7);
tree2_root->left->left = new Tree_Node(6);
tree2_root->left->left->right = new Tree_Node(10);
tree2_root->right->right = new Tree_Node(13);
if (CheckTwoBSTs(tree1_root, tree2_root))
cout << "YES";
else
cout << "NO";
return 0;
}
Output
Yes
📍Time complexity: O(n)
We had used unordered_map’s search and insert operations take O(1) time.
📍Auxiliary Space: O(n) We used unordered_map to store the elements and their indexes.
An array is a collection of homogeneous values stored at contiguous memory locations. It is like a staircase, in which each value of placed at every step, and elements can be accessed by knowing the stair number (or index number).
What is Hashing?
Hashing is a technique using which a given value can be transformed into another value. It makes searching more accessible and quicker.
What is an unordered set in data structure?
An unordered set is a data structure that is an associative container that holds a collection of singular Key objects. Average constant-time complexity characterizes search, insertion, and removal. Internally, the components are arranged into buckets rather than being sorted in any specific sequence.
Whаt аre the three bаsic operаtions on а hаsh tаble?
There are mainly three basic operations of a hash table. Insert − inserts аn element in а hаsh tаble. Seаrch − Seаrches аn element in а hаsh tаble. Delete − Deletes аn element from а hаsh tаble.
What does an unordered set mean?
An unordered set is an associative container with a collection of singular Key objects. The complexity of search, insertion, and removal is often constant-time. Internally, the components are arranged into buckets rather than sorted in any specific sequence.
Conclusion ✉️
In this article, we have extensively discussed the problem BSTs contain the same set of elements or not. We hope that this blog has helped you enhance your knowledge of the tree data structure and set traversal and if you would like to learn more, check out our articles on
305+ registered