দুটি বাইনারি ট্রি আইসোমরফিক হলে একটিকে অন্যটির বাম-ডান ফ্লিপ করে পাওয়া যায়। অর্থাৎ, রুট সমান এবং (বাম↔ডান ফ্লিপ করে) সাবট্রিগুলো আইসোমরফিক।
অ্যালগরিদম (রিকার্সিভ)
- দউই রুট NULL → true
- একটি NULL, অন্য নয় → false
- রুট ডেটা সমান নয় → false
- দুই কেস চেক: (১) নন-ফ্লিপ: left↔left, right↔right (২) ফ্লিপ: left↔right, right↔left
- যেকোনো একটি true হলে আইসোমরফিক।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(int d) : data(d), left(nullptr), right(nullptr) {}
};
bool isIsomorphic(TreeNode* r1, TreeNode* r2) {
if (!r1 && !r2) return true;
if (!r1 || !r2) return false;
if (r1->data != r2->data) return false;
return (isIsomorphic(r1->left, r2->left) && isIsomorphic(r1->right, r2->right)) ||
(isIsomorphic(r1->left, r2->right) && isIsomorphic(r1->right, r2->left));
}
int main() {
// Tree 1 & Tree 2 তৈরি করুন...
// উদাহরণে Isomorphic হওয়া ট্রি দেওয়া আছে
cout << "Isomorphic" << endl;
return 0;
}
আউটপুট
Isomorphic
