এই সমস্যায়, আমরা একটি বাইনারি গাছ দেওয়া হয়. আমাদের কাজ হল বাইনারি ট্রিতে একটি প্রদত্ত নোডের আয়না খুঁজে পাওয়া। আমাদের একটি নোড দেওয়া হবে, এবং সেই নোডের মিরর ইমেজটি বিপরীত সাবট্রিতে খুঁজে পাব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
আউটপুট
mirror of B is E.
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ সমাধান হল বাম সাবট্রি এবং ডান সাবট্রির জন্য দুটি পয়েন্টার ব্যবহার করে রুট থেকে রিকারশন ব্যবহার করে। তারপর লক্ষ্য মানের জন্য যদি কোনো আয়না পাওয়া যায় তাহলে মিরর ফেরত দিন অন্যথায় অন্য নোডগুলি পুনরাবৃত্তি করুন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* left, *right;
};
struct Node* newNode(int key){
struct Node* n = (struct Node*) malloc(sizeof(struct Node*));
if (n != NULL){
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
else{
cout << "Memory allocation failed!"
<< endl;
exit(1);
}
}
int mirrorNodeRecur(int node, struct Node* left, struct Node* right){
if (left == NULL || right == NULL)
return 0;
if (left->key == node)
return right->key;
if (right->key == node)
return left->key;
int mirrorNode = mirrorNodeRecur(node, left->left, right->right);
if (mirrorNode)
return mirrorNode;
mirrorNodeRecur(node, left->right, right->left);
}
int findMirrorNodeBT(struct Node* root, int node) {
if (root == NULL)
return 0;
if (root->key == node)
return node;
return mirrorNodeRecur(node, root->left, root->right);
}
int main() {
struct Node* root = newNode(1);
root-> left = newNode(2);
root->left->left = newNode(3);
root->left->left->left = newNode(4);
root->left->left->right = newNode(5);
root->right = newNode(6);
root->right->left = newNode(7);
root->right->right = newNode(8);
int node = root->left->key;
int mirrorNode = findMirrorNodeBT(root, node);
cout<<"The node is root->left, value : "<<node<<endl;
if (mirrorNode)
cout<<"The Mirror of Node "<<node<<" in the binary tree is
Node "<<mirrorNode;
else
cout<<"The Mirror of Node "<<node<<" in the binary tree is
not present!";
node = root->left->left->right->key;
mirrorNode = findMirrorNodeBT(root, node);
cout<<"\n\nThe node is root->left->left->right, value :
"<<node<<endl;
if (mirrorNode)
cout<<"The Mirror of Node "<<node<<" in the binary tree is
Node "<<mirrorNode;
else
cout<<"The Mirror of Node "<<node<<" in the binary tree is
not present!";
} আউটপুট
The node is root->left, value : 2 The Mirror of Node 2 in the binary tree is Node 6 The node is root->left->left->right, value : 5 The Mirror of Node 5 in the binary tree is not present!
