এই সমস্যায়, আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে এবং বাইনারি গাছের দুটি নোড সংজ্ঞায়িত করা হয়েছে। এবং আমাদের নোডের সমস্ত সাধারণ পূর্বপুরুষ অর্থাৎ সাধারণ নোডগুলিকে প্রিন্ট করতে হবে যা রুট থেকে নোডের ট্রাভার্সাল থেকে নোডের পথে ঘটে।
বাইনারি ট্রি একটি বিশেষ গাছ যার প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড নোড থাকে। সুতরাং, প্রতিটি নোড হয় একটি লিফ নোড বা একটি বা দুটি চাইল্ড নোড রয়েছে৷
উদাহরণ,
পূর্বপুরুষ নোড৷ একটি নোড যা একটি গাছের নিম্ন-স্তরের নোডের সাথে সংযুক্ত।
সাধারণ পূর্বপুরুষ নোড দুটি নোডের একটি নোড যা একটি গাছের উভয় নোডের পূর্বপুরুষ নোড।
উদাহরণস্বরূপ - 
উপরের বাইনারি ট্রিতে, আমাদের 0 এবং 6-এর সাধারণ পূর্বপুরুষ খুঁজে বের করতে হবে।
আউটপুট − 3, 2
এখন, এই সমস্যার উপর ভিত্তি করে, আসুন এই সমস্যাটি সমাধানের জন্য একটি অ্যালগরিদম তৈরি করি,
অ্যালগরিদম
Step 1 : Find the lowest common ancestor of the two nodes of the given tree. And print it. Step 2 : Traverse upward to the root node and print all the nodes that come in the path.
উদাহরণ
এখন, এই সমস্যার সমাধান ব্যাখ্যা করার জন্য একটি প্রোগ্রাম তৈরি করা যাক,
#include <iostream>
using namespace std;
struct Node {
struct Node* left, *right;
int key;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
struct Node* LowestCommonAncestors(struct Node* root, int n1, int n2){
if (root == NULL)
return NULL;
if (root->key == n1 || root->key == n2)
return root;
Node* left_lca = LowestCommonAncestors(root->left, n1, n2);
Node* right_lca = LowestCommonAncestors(root->right, n1, n2);
if (left_lca && right_lca)
return root;
return (left_lca != NULL) ? left_lca : right_lca;
}
bool printAncestorNodes(struct Node* root, int target){
if (root == NULL)
return false;
if (root->key == target) {
cout << root->key << "\t";
return true;
}
if (printAncestorNodes(root->left, target) ||
printAncestorNodes(root->right, target)) {
cout << root->key << "\t”;
return true;
}
return false;
}
bool printcommonAncestors(struct Node* root, int first, int second){
struct Node* LCA = LowestCommonAncestors(root, first, second);
if (LCA == NULL)
return false;
printAncestorNodes(root, LCA->key);
}
int main(){
Node* root = insertNode(24);
root->left = insertNode(8);
root->right = insertNode(69);
root->left->left = insertNode(12);
root->left->right = insertNode(41);
root->right->left = insertNode(50);
root->right->right = insertNode(3);
root->left->left->left = insertNode(22);
root->right->left->left = insertNode(10);
root->right->left->right = insertNode(6);
if (printcommonAncestors(root, 6, 3) == false)
cout << "No Common nodes";
return 0;
} আউটপুট
69 24
