मान लीजिए कि हमारे पास दो बाइनरी ट्री हैं। हमें दो पेड़ों का पहला पत्ता ढूंढना है, जो मेल नहीं खाता। यदि मेल न खाने वाले पत्ते नहीं हैं, तो कुछ भी प्रदर्शित न करें।
अगर ये दो पेड़ हैं, तो पहले गैर-मिलान पत्ते 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