इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है और हमें उसके नोड के पूर्वज को बाइनरी ट्री में प्रिंट करना होता है।
बाइनरी ट्री एक विशेष वृक्ष है जिसके प्रत्येक नोड में अधिकतम दो बच्चे नोड होते हैं। इसलिए, प्रत्येक नोड या तो लीफ नोड होता है या उसमें एक या दो चाइल्ड नोड होते हैं।
उदाहरण,
पूर्वज बाइनरी ट्री में एक नोड एक नोड होता है जो दिए गए नोड के ऊपरी स्तर पर होता है।
आइए पूर्वज नोड का एक उदाहरण लेते हैं -
इस बाइनरी ट्री में मान 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