जांचें कि बाइनरी ट्री (बीएसटी नहीं) में सी ++ में डुप्लिकेट मान है या नहीं

मान लें कि हमारे पास एक बाइनरी ट्री है, यह बाइनरी ट्री 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.