How to find ancestor of a node?

Question

for example in above tree ancestor of 7 is : 7 3 1

Answer 1

I have used level Order traversal for inserting an element in Binary Tree. Level Order traversal is implemented by using queue

#include<iostream>
#include<queue>
#include<algorithm>
#include<stdlib.h>
using namespace std;

struct node{
    struct node *left;
    struct node *right;
    int nodeValue;
};
struct node *root=NULL;

 struct node *insertInBinaryTree(struct node *root , int data){
     queue <struct node*> Q;
     struct node *tmp;
     struct node *newNode;
     newNode=(struct node *) malloc(sizeof(struct node));
     newNode->left=newNode->right=NULL;
     newNode->nodeValue=data;

     if(root==NULL){
        root=newNode;
       return root;
     }
     Q.push(root);
     while(!Q.empty()){    //iterate until the queue is empty
        tmp=Q.front();     // dequeue the element which was first in queue
        Q.pop();
        if(tmp->left)
            Q.push(tmp->left);   //pushing element in queue if tmp->left is not empty
        else{
            tmp->left=newNode;   // if empty insert at left hand side
            return root;
        }
        if(tmp->right)
            Q.push(tmp->right);
        else{
            tmp->right=newNode;
            return root;
        }
     }
     return root;
 }

int printAncestor(struct node *tmp, int data){
    if(tmp==NULL)
        return 0;
    if (tmp->nodeValue==data || printAncestor(tmp->left,data) || printAncestor(tmp->right,data)){
        cout << tmp->nodeValue << ' ';
    return 1;
    }
    return 0;
}

 int main(){
   int data;
   cin >> data;
   while(data!=0){
     root=insertInBinaryTree(root,data);
     cin >>data;
   }
   cin >>data;
  printAncestor(root,data);
 }