C++-এ একটি বাইনারি ট্রিতে ডুপ্লিকেট সাবট্রি (সাইজ ২ বা অধিক) আছে কিনা চেক করা

মনে করুন একটি বাইনারি ট্রি আছে। আমাদের খুঁজে বের করতে হবে ট্রিতে সাইজ ২ বা অধিক ডুপ্লিকেট সাবট্রি আছে কিনা। ধরুন একটি বাইনারি ট্রি নিচের মতো:

এখানে সাইজ ২-এর দুটি অভিন্ন সাবট্রি আছে। এই সমস্যাটি ট্রি সিরিয়ালাইজেশন এবং হ্যাশিং প্রসেস দিয়ে সমাধান করা যায়। আইডিয়া হল সাবট্রিগুলোকে স্ট্রিং আকারে সিরিয়ালাইজ করা এবং হ্যাশ টেবিলে রাখা। একবার আমরা একটি সিরিয়ালাইজড ট্রি পাই যা লিফ নয়, এবং যা ইতিমধ্যে হ্যাশ টেবিলে আছে, তবে true রিটার্ন করুন।

উদাহরণ কোড

#include <iostream>
#include <unordered_set>
using namespace std;

const char MARKER = '$';

struct Node {
public:
    char key;
    Node *left, *right;
};

Node* getNode(char key) {
    Node* newNode = new Node;
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

unordered_set<string> subtrees;

string duplicateSubtreeFind(Node *root) {
    string res = "";
    if (root == NULL) // কারেন্ট নোড NULL হলে $ রিটার্ন
        return res + MARKER;
    string l_Str = duplicateSubtreeFind(root->left);
    if (l_Str.compare(res) == 0)
        return res;
    string r_Str = duplicateSubtreeFind(root->right);
    if (r_Str.compare(res) == 0)
        return res;
    res = res + root->key + l_Str + r_Str;
    if (res.length() > 3 && subtrees.find(res) != subtrees.end()) // সাবট্রি ইতিমধ্যে আছে
        return "";
    subtrees.insert(res);
    return res;
}

int main() {
    Node *root = getNode('A');
    root->left = getNode('B');
    root->right = getNode('C');
    root->left->left = getNode('D');
    root->left->right = getNode('E');
    root->right->right = getNode('B');
    root->right->right->right = getNode('E');
    root->right->right->left = getNode('D');
    string str = duplicateSubtreeFind(root);
    if (str.compare("") == 0)
        cout << "It has dublicate subtrees of size more than 1";
    else
        cout << "It has no dublicate subtrees of size more than 1";
    return 0;
}

আউটপুট

It has dublicate subtrees of size more than 1