মনে করুন একটি বাইনারি ট্রি আছে, এটি BST নয়। আমাদের চেক করতে হবে বাইনারি ট্রিতে একই এলিমেন্ট একাধিকবার আছে কিনা। এটি সমাধান করতে হ্যাশিং ব্যবহার করব। দেওয়া ট্রি ট্রাভার্স করব, প্রতিটি নোডের জন্য চেক করব নোডটি টেবিলে আছে কিনা, যদি ইতিমধ্যে থাকে তবে false রিটার্ন করুন, অন্যথায় true।
উদাহরণ কোড
#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.";
return 0;
}
আউটপুট
The tree has duplicate elements.
