top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to find ancestor of a node?

+1 vote
287 views

enter image description here

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

posted Jun 14, 2016 by Shubham Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

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);
 }
answer Jun 14, 2016 by Shahsikant Dwivedi
Similar Questions
+7 votes

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm/code for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

+7 votes
                    10
                    /  \                    
                   7     15
                  / \    / \
                 6   8  12  18
                /     \
               5       9
            (Given Binary tree) 
+4 votes

I have tried bruteforce method but it's complexity is of O(n^2) , i am interested in O(n) or O(nlon n)
enter image description here

for the tree given above common ancestor of node 1 and 7 is 4. I am much interested in function not the whole program,function shoud take three argument as root of the tree, node1 and node 2

0 votes

Give program time complexity as well as.

...