ধরুন আমাদের দুটি বাইনারি গাছ আছে। দুটি গাছের প্রথম পাতা খুঁজে বের করতে হবে, তা মেলে না। যদি কোন অ-মেলা পাতা না থাকে, তাহলে কিছুই প্রদর্শন করুন।
যদি এই দুটি গাছ হয়, তাহলে প্রথম অমিল পাতা হল 11 এবং 15টি৷
এখানে আমরা স্ট্যাক ব্যবহার করে একই সাথে উভয় গাছের পুনরাবৃত্তিমূলক প্রি-অর্ডার ট্রাভার্সাল ব্যবহার করব। আমরা বিভিন্ন গাছের জন্য বিভিন্ন স্ট্যাক ব্যবহার করব। উপরের নোডটি লিফ নোড না হওয়া পর্যন্ত আমরা নোডগুলিকে স্ট্যাকের মধ্যে ঠেলে দেব। দুটি শীর্ষের তুলনা করুন, যদি তারা একই হয়, তাহলে আরও পরীক্ষা করুন, অন্যথায় দুটি স্ট্যাক শীর্ষ উপাদান দেখান৷
উদাহরণ
#include <iostream>
#include <stack>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node *getNode(int x) {
Node * newNode = new Node;
newNode->data = x;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isLeaf(Node * t) {
return ((t->left == NULL) && (t->right == NULL));
}
void findUnmatchedNodes(Node *t1, Node *t2) {
if (t1 == NULL || t2 == NULL)
return;
stack<Node*> s1, s2;
s1.push(t1); s2.push(t2);
while (!s1.empty() || !s2.empty()) {
if (s1.empty() || s2.empty() )
return;
Node *top1 = s1.top();
s1.pop();
while (top1 && !isLeaf(top1)){
s1.push(top1->right);
s1.push(top1->left);
top1 = s1.top();
s1.pop();
}
Node * top2 = s2.top();
s2.pop();
while (top2 && !isLeaf(top2)){
s2.push(top2->right);
s2.push(top2->left);
top2 = s2.top();
s2.pop();
}
if (top1 != NULL && top2 != NULL ){
if (top1->data != top2->data ){
cout << "First non matching leaves are: "<< top1->data <<" "<< top2->data<< endl;
return;
}
}
}
}
int main() {
Node *t1 = getNode(5);
t1->left = getNode(2);
t1->right = getNode(7);
t1->left->left = getNode(10);
t1->left->right = getNode(11);
Node * t2 = getNode(6);
t2->left = getNode(10);
t2->right = getNode(15);
findUnmatchedNodes(t1,t2);
} আউটপুট
First non matching leaves are: 11 15
