বাইনারি ট্রিতে কাজিন নোড খুঁজে বের করা C++-এ

একটি বাইনারি ট্রিতে দুটি নোড কাজিন হয় যদি তারা একই গভীরতায় (depth) থাকে কিন্তু তাদের পিতামাতা (parent) আলাদা হয়। রুট নোডের গভীরতা ০। ট্রির সব মান یونিক। দেওয়া দুটি মান x এবং y ক্যাজিন কিনা তা যাচাই করতে হবে।

উদাহরণ

ট্রি:

      1
     / \
    2   3
     \   \
      4   5

x = 5, y = 4 → আউটপুট: true (একই লেভেলে, ভিন্ন প্যারেন্ট)

অ্যালগরিদম (BFS লেভেল-অর্ডার)

1. একটি কিউ এবং প্যারেন্ট ম্যাপ (unordered_map) রাখুন।
2. রুট কিউতে পুশ করুন।
3. প্রতি লেভেল প্রসেস করুন:
   • বর্তমান লেভেলের সব নোডের জন্য চাইল্ড চেক করুন।
   • চাইল্ডের মান x বা y হলে তার প্যারেন্ট ম্যাপে সংরক্ষণ করুন।
   • চাইল্ড কিউতে পুশ করুন।
4. লেভেল শেষে যদি x এবং y উভয়ই পাওয়া যায়:
   • যদি প্যারেন্ট ভিন্ন হয় → true রিটার্ন করুন।
   • অন্যথায় false।
5. ট্রাই ভাঙলে false রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        unordered_map parent;
        queue q;
        q.push(root);
        parent[x] = parent[y] = nullptr;
        
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                TreeNode* cur = q.front(); q.pop();
                if (cur->left) {
                    if (cur->left->val == x || cur->left->val == y)
                        parent[cur->left->val] = cur;
                    else
                        q.push(cur->left);
                }
                if (cur->right) {
                    if (cur->right->val == x || cur->right->val == y)
                        parent[cur->right->val] = cur;
                    else
                        q.push(cur->right);
                }
            }
            if (parent[x] || parent[y]) {
                if (!parent[x] || !parent[y] || parent[x] == parent[y])
                    return false;
                return true;
            }
        }
        return false;
    }
};

int main() {
    Solution ob;
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(5);
    cout << (ob.isCousins(root, 5, 4) ? "true" : "false");
    return 0;
}

ইনপুট

TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(4); root->right->right = new TreeNode(5); ob.isCousins(root, 5, 4)

আউটপুট

1 (true)