# Check if two BSTs contain same set of elements

Given two Binary Search Trees consisting of unique positive elements, we have to check whether the two BSTs contains same set or elements or not.
Note: The structure of the two given BSTs can be different.
For example, The above two BSTs contains same set of elements {5, 10, 12, 15, 20, 25}

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1: The most simple method will be to traverse first tree and store its element in a list or array. Now, traverse 2nd tree and simultaneously check if the current element is present in the list or not. If yes, then mark the element in the list as negative and check for further elements otherwise if no, then immediately terminate the traversal and print No. If all the elements of 2nd tree is present in the list and are marked negative then finally traverse the list to check if there are any non-negative elements left. If Yes then it means that the first tree had some extra element otherwise the both tree consists same set of elements.

Time Complexity: O( n * n ) , where n is the number of nodes in the BST.
Auxiliary Space: O( n ).

Method 2: This method is an optimization of above approach. If we observe carefully, we will see that in the above approach, search for element in the list takes linear time. We can optimize this operation to be done in constant time using a hashmap instead of list. We insert elements of both trees in different hash sets. Finally we compare if both hash sets contain same elements or not.

Below is the complete implementation of above approach:

 `// CPP program to check if two BSTs contains ` `// same set of elements ` `#include ` `using` `namespace` `std; ` ` `  `// BST Node ` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `// Utility function to create new Node ` `Node* newNode(``int` `val) ` `{ ` `    ``Node* temp = ``new` `Node; ` `    ``temp->data = val; ` `    ``temp->left = temp->right = NULL;  ` `    ``return` `temp; ` `} ` ` `  `// function to insert elements of the  ` `// tree to map m ` `void` `insertToHash(Node* root, unordered_set<``int``> &s) ` `{ ` `    ``if` `(!root) ` `        ``return``; ` `    ``insertToHash(root->left, s); ` `    ``s.insert(root->data); ` `    ``insertToHash(root->right, s); ` `} ` ` `  `// function to check if the two BSTs contain ` `// same set  of elements ` `bool` `checkBSTs(Node* root1, Node* root2) ` `{  ` `    ``// Base cases  ` `    ``if` `(!root1 && !root2)  ` `        ``return` `true``; ` `    ``if` `((root1 && !root2) || (!root1 && root2)) ` `        ``return` `false``; ` `         `  `    ``// Create two hash sets and store  ` `    ``// elements both BSTs in them. ` `    ``unordered_set<``int``> s1, s2; ` `    ``insertToHash(root1, s1); ` `    ``insertToHash(root2, s2); ` ` `  `    ``// Return true if both hash sets  ` `    ``// contain same elements. ` `    ``return` `(s1 == s2); ` `} ` ` `  `// Driver program to check above functions ` `int` `main() ` `{  ` `    ``// First BST ` `    ``Node* root1 = newNode(15); ` `    ``root1->left = newNode(10); ` `    ``root1->right = newNode(20); ` `    ``root1->left->left = newNode(5); ` `    ``root1->left->right = newNode(12); ` `    ``root1->right->right = newNode(25); ` `     `  `    ``// Second BST ` `    ``Node* root2 = newNode(15); ` `    ``root2->left = newNode(12); ` `    ``root2->right = newNode(20); ` `    ``root2->left->left = newNode(5); ` `    ``root2->left->left->right = newNode(10); ` `    ``root2->right->right = newNode(25); ` `     `  `    ``// check if two BSTs have same set of elements ` `    ``if` `(checkBSTs(root1, root2)) ` `        ``cout << ``"YES"``; ` `    ``else` `        ``cout << ``"NO"``; ` `    ``return` `0;         ` `} `

Output:

```YES
```

Time Complexity: O( n ), where n is the number of nodes in the trees.
Auxiliary Space: O( n ).

Method 3 : We know about an interesting property of BST that inorder traversal of a BST generates a sorted array. So we can do inorder traversals of both the BSTs and generate two arrays and finally we can compare these two arrays. If both of the arrays are same then the BSTs have same set of elements otherwise not.

 `// CPP program to check if two BSTs contains ` `// same set of elements ` `#include ` `using` `namespace` `std; ` ` `  `// BST Node ` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `// Utility function to create new Node ` `Node* newNode(``int` `val) ` `{ ` `    ``Node* temp = ``new` `Node; ` `    ``temp->data = val; ` `    ``temp->left = temp->right = NULL;  ` `    ``return` `temp; ` `} ` ` `  `// function to insert elements of the  ` `// tree to map m ` `void` `storeInorder(Node* root, vector<``int``> &v) ` `{ ` `    ``if` `(!root) ` `        ``return``; ` `    ``storeInorder(root->left, v); ` `    ``v.push_back(root->data); ` `    ``storeInorder(root->right, v); ` `} ` ` `  `// function to check if the two BSTs contain ` `// same set  of elements ` `bool` `checkBSTs(Node* root1, Node* root2) ` `{  ` `    ``// Base cases  ` `    ``if` `(!root1 && !root2)  ` `        ``return` `true``; ` `    ``if` `((root1 && !root2) || (!root1 && root2)) ` `        ``return` `false``; ` `         `  `    ``// Create two vectors and store  ` `    ``// inorder traversals of both BSTs  ` `    ``// in them. ` `    ``vector<``int``> v1, v2; ` `    ``storeInorder(root1, v1); ` `    ``storeInorder(root2, v2); ` ` `  `    ``// Return true if both vectors are ` `    ``// identical ` `    ``return` `(v1 == v2); ` `} ` ` `  `// Driver program to check above functions ` `int` `main() ` `{  ` `    ``// First BST ` `    ``Node* root1 = newNode(15); ` `    ``root1->left = newNode(10); ` `    ``root1->right = newNode(20); ` `    ``root1->left->left = newNode(5); ` `    ``root1->left->right = newNode(12); ` `    ``root1->right->right = newNode(25); ` `     `  `    ``// Second BST ` `    ``Node* root2 = newNode(15); ` `    ``root2->left = newNode(12); ` `    ``root2->right = newNode(20); ` `    ``root2->left->left = newNode(5); ` `    ``root2->left->left->right = newNode(10); ` `    ``root2->right->right = newNode(25); ` `     `  `    ``// check if two BSTs have same set of elements ` `    ``if` `(checkBSTs(root1, root2)) ` `        ``cout << ``"YES"``; ` `    ``else` `        ``cout << ``"NO"``; ` `    ``return` `0;         ` `} `

Output:

```YES
```

Time Complexity: O( n ).
Auxiliary Space: O( n ).