এই সমস্যায়, আমাদের দুটি ট্রি দেওয়া আছে। আমাদের কাজ হল দুটি ট্রি আইডেন্টিক্যাল কিনা তা চেক করার একটি কোড লিখা।
দুটি ট্রি আইডেন্টিক্যাল বলা হয় যদি অ্যারে এলিমেন্টগুলো একই ভ্যালু এবং একই অরিয়েন্টেশনে থাকে।
উদাহরণ
যেহেতু দুটি ট্রির একই ভ্যালু এবং এলিমেন্টের পজিশন একই, তাই দুটি ট্রি আইডেন্টিক্যাল।
দুটি ট্রি আইডেন্টিক্যাল কিনা চেক করতে, আমরা নোড বাই নোড প্রতিটি নোডে যাব এবং সেগুলোর ইকুয়ালিটি ধাপে ধাপে চেক করব এবং যদি কোনো পয়েন্টে দুটি নোড সমান না হয় তবে -1 রিটার্ন করব, যা ইঙ্গিত করে ট্রিগুলো আইডেন্টিক্যাল নয় এবং যদি পুরো ট্রি ট্রাভার্স হয় বা দুটি ট্রি খালি হয় তবে ১ রিটার্ন করব, যা ইঙ্গিত করে ট্রিগুলো আইডেন্টিক্যাল।
উপরোক্ত সমাধানের কাজ করার পদ্ধতি ইলাস্ট্রেট করার প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int isIdentricalTrees(node* tree1, node* tree2) {
if (tree1 == NULL && tree2 == NULL)
return 1;
if (tree1 != NULL && tree2 != NULL) {
return( tree1->data == tree2->data && isIdentricalTrees(tree1->left, tree2->left) && isIdentricalTrees(tree1->right, tree2->right) );
}
return 0;
}
int main() {
node *root1 = insertNode(4);
node *root2 = insertNode(4);
root1->left = insertNode(5);
root1->right = insertNode(0);
root1->left->left = insertNode(1);
root1->left->right = insertNode(9);
root1->right->left = insertNode(7);
root2->left = insertNode(5);
root2->right = insertNode(0);
root2->left->left = insertNode(1);
root2->left->right = insertNode(9);
root2->right->left = insertNode(7);
cout << "Both the given trees are ";
if (isIdentricalTrees(root1, root2))
cout << "identical";
else
cout << "not identical";
return 0;
}
আউটপুট
Both the given trees are identical
