समस्या विवरण
एक बाइनरी ट्री (BST नहीं) दिया गया है, जांचें कि क्या इसमें कोई डुप्लिकेट मान है।
हल: हैशिंग
ट्री ट्रैवर्स करें, प्रत्येक नोड के लिए हैश सेट में जांचें। यदि पहले से मौजूद है → डुप्लिकेट है।
उदाहरण कोड
#include <iostream>
#include <unordered_set>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
bool hasDuplicateHelper(Node* root, unordered_set& 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 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.
