এই সমস্যায়, আমাদের একটি বাইনারি গাছ এবং বাইনারি গাছের দুটি নোড দেওয়া হয়েছে। আমাদের কাজ হল দুটি নোডের মধ্যবর্তী পথে আসা সমস্ত নোডের 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
