একটি বাইনারি ট্রি যদি নিজের মিরর ইমেজ তৈরি করে, তবে তাকে সিমেট্রিক ট্রি বলা হয়। অর্থাৎ, বাম সাবট্রি এবং ডান সাবট্রি একে অপরের মিরর হবে।
অ্যালগরিদম
- রিকার্সিভ হেল্পার ফাংশন যা দুটি নোড (রুট1, রুট2) নেয়।
- দউই নোড NULL হলে true রিটার্ন।
- একটি NULL, অন্য নয় হলে false।
- ডেটা সমান হলে: বামের বাম ↔ ডানের ডান এবং বামের ডান ↔ ডানের বাম রিকার্সিভলি চেক।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int data;
TreeNode *left, *right;
};
TreeNode* createNode(int d) {
TreeNode* root = new TreeNode;
root->data = d;
root->left = root->right = NULL;
return root;
}
bool helper(TreeNode* root1, TreeNode* root2) {
if (!root1 && !root2) return true;
if (!root1 || !root2) return false;
return (root1->data == root2->data) &&
helper(root1->left, root2->right) &&
helper(root1->right, root2->left);
}
bool isSymmetric(TreeNode* root) {
return helper(root, root);
}
int main() {
TreeNode* root = createNode(4);
root->left = createNode(2);
root->right = createNode(2);
root->left->left = createNode(5);
root->left->right = createNode(7);
root->right->left = createNode(5);
root->right->right = createNode(7);
cout << (isSymmetric(root) ? "True" : "False") << endl;
return 0;
}
আউটপুট
True
দেওয়া ট্রিটি সিমেট্রিক, তাই আউটপুট True।
