আমাদের একটি বাইনারি গাছ আছে বিবেচনা করুন, এই বাইনারি গাছ একটি BST নয়. বাইনারি ট্রিতে একই উপাদান একাধিকবার আছে কি না তা আমাদের পরীক্ষা করতে হবে। এটি সমাধান করার জন্য, আমরা হ্যাশিং ব্যবহার করব। আমরা প্রদত্ত গাছটি অতিক্রম করব, প্রতিটি নোডের জন্য, আমরা পরীক্ষা করব যে নোডটি টেবিলে উপস্থিত আছে কি না, যদি এটি ইতিমধ্যে উপস্থিত থাকে তবে মিথ্যা ফেরত দিন, অন্যথায় সত্য৷
উদাহরণ
#include <iostream>
#include <unordered_set>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
};
Node* getNode(int data){
Node *newNode = new Node;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
bool hasDuplicateHelper(Node *root, unordered_set<int> &s){
if(root == NULL)
return false;
if (s.find(root->data) != s.end())
return true;
s.insert(root->data);
return hasDuplicateHelper(root->left, s) || hasDuplicateHelper(root->right, s);
}
bool hasDuplicate(Node *root){
unordered_set<int> s;
return hasDuplicateHelper(root, s);
}
int main() {
Node *root = getNode(10);
root->left = getNode(20);
root->right = getNode(20);
root->left->left = getNode(30);
if (hasDuplicate(root))
cout << "The tree has duplicate elements.";
else
cout << "The tree has no duplicate elements.";
} আউটপুট
The tree has duplicate elements.
