इस समस्या में, हमें एक बाइनरी ट्री दिया गया है और हमें बाइनरी ट्री में एक नोड के पूर्वजों को प्रिंट करना है।
बाइनरी ट्री एक विशेष ट्री है जिसका प्रत्येक नोड अधिकतम दो चाइल्ड नोड रख सकता है। तो, प्रत्येक नोड या तो एक लीफ नोड होता है या उसके एक या दो चाइल्ड नोड होते हैं।
उदाहरण,
बाइनरी ट्री में एक नोड का पूर्वज एक नोड है जो दिए गए नोड के ऊपरी स्तर पर है।
आइए पूर्वज नोड का एक उदाहरण लें -
इस बाइनरी ट्री में मान 3 वाले नोड के पूर्वज 8 हैं,
इस समस्या को हल करने के लिए, हम रूट नोड से टारगेट नोड तक ट्रैवर्स करेंगे। बाइनरी ट्री में चरण दर चरण नीचे की ओर। और पथ में आने वाले सभी नोड्स को प्रिंट करेंगे।
उदाहरण
#include<iostream> #include<stdio.h> #include<stdlib.h> using namespace std; struct node{ int data; struct node* left; struct node* right; }; bool AncestorsNodes(struct node *root, int target){ if (root == NULL) return false; if (root->data == target) return true; if ( AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target) ){ cout << root->data << " "; return true; } return false; } struct node* insertNode(int data){ struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } int main(){ struct node *root = insertNode(10); root->left = insertNode(6); root->right = insertNode(13); root->left->left = insertNode(3); root->left->right = insertNode(8); root->right->left = insertNode(12); cout<<"Ancestor Nodes are " ; AncestorsNodes(root, 8); getchar(); return 0; } आउटपुट
Ancestor Nodes are 6 10
