Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction 📝
2.
Problem Statement 🖥️
3.
Explanation 📇
4.
Approach ⚙️
4.1.
Naive Approach 🎛️
4.2.
Efficient approach
4.3.
Algorithm 🌐
4.4.
Code 📝
5.
Frequently Asked Question ❓
5.1.
What is an array?
5.2.
What is Hashing?
5.3.
What is an unordered set in data structure?
5.4.
Whаt аre the three bаsic operаtions on а hаsh tаble?
5.5.
What does an unordered set mean?
6.
Conclusion ✉️
Last Updated: Mar 27, 2024
Easy

# Check if two BSTs contain the same set of elements or not

Alok Pandey
0 upvote

## Introduction 📝

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]

You can also read about insertion into bst.

## Approach ⚙️

There can be multiple approaches to solve this problem we will discuss some of them:

### Naive Approach 🎛️

1. Traverse the first tree and store its element in a list or array.

2. Traverse another tree and check whether the current element is present in the list.

3. If yes, mark the element in the list as negative and search for more elements.

4. If no, then terminate the traversal and print No.

5.  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.

6. If yes, then the first tree has an extra element; else, both trees have the same set of elements.

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

📍Auxiliary Space: O( n ).

### Efficient approach

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.
• Compare both sets.
• If they are the same, return true, Else false.

### Code 📝

``````/* 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 complexityO(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.

Check out this problem - Mirror A Binary Tree

## Frequently Asked Question ❓

### What is an array?

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

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Enroll in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!

Live masterclass