Problem
You’re given a root of a binary tree and a key k. You need to print the ancestors of k in the given binary tree.
For the given Binary tree, if k = 31, it should print: 10 21
Pseudocode
1. Traverse the given binary tree in a preorder fashion. 2. do if info[root] == key, return true 3. Traverse root->left & root->right 4. if traverse(root->left) || traverse(root->right) is true 5. print (info[root]) Since it is in the path to key k 6. end
Let the given tree be:
Code Implementation
//
// main.cpp
// Ancestors of a node
//
// Created by Himanshu on 15/09/21.
//
#include <iostream>
#include <queue>
using namespace std;
struct node {
int info = 0;
struct node *left, *right;
};
typedef struct node Node;
node* newNode(int data)
{
node* Node = new node();
Node->info = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
bool ancestor (Node *root, int key) {
if (!root) {
return false;
} else if (root->info == key) {
return true;
}
if ((ancestor (root->left, key)) || (ancestor (root->right, key))) {
cout<<(root->info)<<" ";
return true;
}
return false;
}
int main() {
Node *root = newNode(1);
root->left = newNode(20);
root->right = newNode(21);
root->right->left = newNode(30);
root->right->right = newNode(31);
root->right->right->left = newNode(40);
root->right->right->left->right = newNode(51);
cout<<"The ancestors of 30 are: "<<endl;
ancestor(root, 30);
cout<<endl;
cout<<"The ancestors of 51 are: "<<endl;
ancestor(root, 51);
cout<<endl;
return 0;
}
Output
The ancestors of 30 are: 21 1 The ancestors of 51 are: 40 31 21 1
Time complexity of the above solution is O(n), where n is the number of nodes in tree. This is because each node of the tree is traversed only once.
Here’s a working example: Binary tree (Print Ancestors)
8 thoughts on “How to print ancestors of a node in Binary tree using C++”
Thank you for great content. I look forward to the continuation. newsmax tv live streaming
Bardzo ciekawy blog, rzeczowy i wyważony. Od dzisiaj zaglądam regularnie i subsbskrybuje kanał RSS. Pozdrowienia 🙂
Nie wiem czy wiesz ale tworzysz bardzo ciekawe i inspirujące treści. Trzymaj dalej tak wysoki poziom, a już wkrótce osiągniesz szczyty wyszukiwarek na topowe frazy 🙂
Naprawdę podoba mi się twój szablon wp zwłaszcza ostylowanie CSS, skąd go pobrałeś? Z góry dziękuję!
Czy wiesz, że tworzysz ciekawe i oryginalne treści, wkład jaki wnosisz w społeczność blogową zasługuję na podziw i szacunek,trzymaj tak dalej i nie zasypiaj gruszek w popiele. Dzięki!
Dziękuję Ci
Prawdziwy z Ciebie talent i mistrz pióra z ogromną łatwością przekładasz myśli na słowa… trzymaj tak dalej, dbaj i pięlęgnuj swego bloga… Czym się inspirujesz na codzień ? skad czerpiesz pomysły na wpisy ?
Dziękuję Ci