How to print ancestors of a node in Binary tree using C++

By onlycode_oz40jdTrees

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.

binary tree
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++”

  1. 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 ?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *