দুটি বাইনারি ট্রি দেওয়া আছে। আমাদের দুটি ট্রির প্রথম লীফ নোড খুঁজে বের করতে হবে যা মেলে না। যদি কোনো অমিল লীফ নেই, তবে কিছুই দেখাব না।
যদি এই দুটি ট্রি হয়, তবে প্রথম অমিল লীফগুলো হবে ১১ এবং ১৫।
এখানে আমরা দুটি ট্রির ইটারেটিভ প্রি-অর্ডার ট্রাভার্সাল (iterative preorder traversal) স্ট্যাক ব্যবহার করে একসাথে করব। দুটি ট্রির জন্য আলাদা স্ট্যাক ব্যবহার করব। লীফ নোড না পাওয়া পর্যন্ত নোডগুলো স্টാക്കে পুশ করব। দুটি স্ট্যাকের টপ তুলনা করব, যদি সেম হয় তবে ফার্দার চেক করব, অন্যথায় দুটি স্ট্যাকের টপ এলিমেন্ট দেখাব।
উদাহরণ
#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
