top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Print cousins of a given node in a tree?

+7 votes
1,981 views

Print cousins of a given node (Not sibling) ??

posted Nov 26, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button
What is the meaning of cousins???
Two nodes who are at the same level but does not have same parent are called cousins.

1 Answer

+1 vote

Step1 : Find the level of the node and parent of the node.
Step 2 : Pass the level and parent. Traverse the tree and print the node if it is at the level passed and does not have same parent.

using namespace std; 

struct node{ 
    struct node* left; 
    struct node* right; 
    int data; 
}; 

void inorder(struct node* root,int present_level,int level,struct node* parent) 
{ 
  if(root!=NULL) 
  { 
   if(parent!=root) 
       inorder(root->left,present_level+1,level,parent); 
   if(level==present_level) 
       cout<<root->data<<" "; 
   if(parent!=root) 
       inorder(root->right,present_level+1,level,parent); 
  } 
} 

void make_tree(struct node **root,int data) 
{ 
    if((*root)==NULL) 
    { 
        (*root)=new node; 
        (*root)->left=NULL; 
        (*root)->right=NULL; 
        (*root)->data=data; 
        return; 
    } 
    else 
    { 
        if (((*root)->data)< data)
            make_tree(&((*root)->right),data); 
        else 
            make_tree(&((*root)->left),data); 
    } 


} 

struct node* find_level_and_parent(struct node* root,int data,int* level) 
{ 
    struct node* parent=NULL; 
    struct node* child=root; 

    while(1) 
    { 
        if(child==NULL) 
            return NULL; 
        if(child->data==data) 
        { 
            return parent; 
        } 
        if(data>child->data) 
        { 
            parent=child; 
            child=child->right; 
            *level=*level+1; 
        } 
        else if(data<=child->data) 
        { 
            parent=child; 
            child=child->left; 
            *level=*level+1; 
        } 
    } 
} 

int main() 
{ 
    struct node* root=NULL; 
    make_tree(&root,6); 
    make_tree(&root,8); 
    make_tree(&root,3); 
    make_tree(&root,4); 
    make_tree(&root,44); 
    make_tree(&root,34); 
    make_tree(&root,12); 
    make_tree(&root,9); 
    make_tree(&root,2); 
    make_tree(&root,1); 
    make_tree(&root,33); 

    print_tree(root);

    int level=0; 
    struct node* temp=find_level_and_parent(root,44,&level); 
    if(temp!=NULL) 
    { 
        inorder(root,0,level,temp);
        return 0; 
    } 
    return 1; 
}

Tested code and is working fine.

answer Nov 26, 2013 by Salil Agrawal
Similar Questions
+7 votes
     50
    /  \
   20   30
   / \
  70  80
 /  \   \
10   40  60        

printing the border elements anticlockwise direction:
->50->20->70->10->40->60->30

+6 votes
The input tree is as shown below
            40
            / \
        20      60
        / \       \
    10      30      80
      \            /  \ 
       15        70    90

Output: 15 30 60 80 90
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...