এই সমস্যায়, আমাদের একটি বাইনারি ট্রি এবং বাইনারি ট্রির দুটি নোড দেওয়া আছে। আমাদের কাজ হল দুটি নোডের মধ্যে আসা সব নোডের XOR প্রিন্ট করা।
একটি উদাহরণ দিয়ে সমস্যাটি বুঝতে পারি,
আমাদের 2 এবং 3-এর মধ্যে XOR বের করতে হবে।
2 থেকে 3-এর পথ: 2 → 6 → 1 → 3।
আমরা 2^3^1^3 বের করব।
আউটপুট —
এই সমস্যাটি সমাধান করতে, আমাদের এক নোড থেকে অন্য নোডে পথ বের করতে হবে। এর জন্য, আমরা রুট থেকে দুটি নোড দুটোর পথের সব নোডের XOR বের করব। রুট নোড থেকে ট্রাভার্স করার সময় দুটি কেস আসে — είথার সোর্স এবং ডেস্টিনেশন নোড দুটো রুট নোডের একই সাইডে থাকে অথবা ভিন্ন সাইডে। প্রথম কেসে, পথে না আসা সব নোড দুইবার ট্রাভার্স হবে এবং ক্যানসেল আউট হবে। আর দ্বিতীয় কেসে পুরো পথ রুট থেকে নোডগুলো বিবেচনা করতে হবে। প্রতিটি স্টেপে আমরা নোডটি আগের XOR রেজাল্টের সাথে XOR করব, এটি স্পেস বাঁচাবে।
উদাহরণ
আমাদের সমাধানের ইমপ্লিমেন্টেশন দেখানোর প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* getNode(int data) {
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void pathStoD(Node* root, unordered_map<int, int>& path, int XOR) {
if (!root)
return;
path.insert(make_pair(root->data, XOR ^ root->data));
XOR ^= root->data;
if (root->left)
pathStoD(root->left, path, XOR);
if (root->right)
pathStoD(root->right, path, XOR);
}
int findPathXOR(unordered_map<int, int> path, int node1, int node2) {
return path[node1] ^ path[node2];
}
int main() {
struct Node* root = getNode(1);
root->left = getNode(6);
root->left->left = getNode(2);
root->left->right = getNode(4);
root->right = getNode(3);
root->right->left = getNode(7);
root->right->right = getNode(5);
int XOR = 0;
unordered_map<int, int> mp;
int source = 2;
int destination = 3;
pathStoD(root, mp, XOR);
cout << "The XOR of all node from " << source << " to " << destination << " of the tree is: ";
cout << findPathXOR(mp, source, destination);
return 0;
}
আউটপুট
The XOR of all node from 2 to 3 of the tree is: 7
