ancestor cpp

// program to print all the ancestors of a node in binary tree
#include <iostream>

using namespace std;

// node class
class node{
public:
    int data;
    node* left;
    node* right;
};

// function that returns a pointer to new node
node* createNode(int element){
    node* temp = (node*) malloc(sizeof(node));
    temp->data = element;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

// function to print all the ancestors of a node
bool ancestors(node* root, int target){
    // if the current node is null then return false
    if(root == NULL){
        return false;
    }
    // if the current node is our target node then we return true
    if(root->data == target){
        return true;
    }
    // here we recursively check if the current node if the ancestor of the target node then we need to print it
    // the target node might lie in the left or the right subtree
    // thus we take or of the the returned boolean values
    if(ancestors(root->left, target) || ancestors(root->right, target)){
        cout<<root->data<<" ";
        return true;
    }

    return false;
}

int main() {

    node* head = createNode(1);
    head->left = createNode(2);
    head->right = createNode(3);
    head->left->left = createNode(4);
    head->left->right = createNode(5);
    head->right->right = createNode(6);
    head->left->left->right = createNode(7);
    head->right->right->left = createNode(8);
    head->left->left->right->left = createNode(9);
    head->left->left->right->left->left = createNode(10);
    head->right->right->left->right = createNode(11);
    cout<<"All ancestors of node 10 are : ";
    ancestors(head, 10);
    cout<<"\nAll ancestors of node 5 are : ";
    ancestors(head, 5);
    cout<<"\nAll ancestors of node 8 are : ";
    ancestors(head, 8);

}

/*

All ancestors of node 10 are : 9 7 4 2 1
All ancestors of node 5 are : 2 1
All ancestors of node 8 are : 6 3 1
Process finished with exit code 0

*/