Check if two nodes are cousins in a Binary Tree in C++

In this C++ programming tutorial, we will see how to check if two nodes are cousins in a binary tree.

Firstly two nodes are cousins when they are at the same depth but they have different parent nodes.e.g.

                                      50
                                    /    \
                                  30      60
                                 /  \    /  \
                               40   10  20   -1

// Here 40 and 20 are cousins as they are at same depth but with different parent nodes.
// while 40 and 10 are not cousins as they have same parent node.

 

Algorithm

  • The algorithm used is simple. We will first make a tree for the given array.
  • Next, we will make a function sameparent() which returns a boolean value. It checks whether the nodes have the same parent or not. The function’s working is pretty simple, it checks whether the children of a node (left and right) contain our desired values or not and returns true if it finds both nodes against one parent node.
  • To be cousins the returned value should be false.
  • Next, we make a function depth() which will return an integer corresponding to the depth of the value. If the function finds the value it returns the depth value else returns 0. We will call this function separately for both the nodes.
  • To be cousins the returned values from both the nodes should be the same.

 

Implementation

Below is the code which implements the above algorithm.

#include <bits/stdc++.h>
using namespace std;

struct tree{
    
  int data;
  tree *left, *right;
  
  tree(int k){
      this->data = k;
      this->left = NULL;
      this->right = NULL;
  }
  
};

tree *maketree(tree *head, int *arr ,int n ,int i){
    if(i<n && arr[i]==-1)
    return NULL;
    
    if(i<n){
    
    tree *temp = new tree(arr[i]);
    head = temp;
    
    head->left = maketree(head->left,arr,n,2*i+1);
    head->right = maketree(head->right,arr,n,2*i +2);
    }
    return head;
    
}

bool sameparent(tree *head ,int x ,int y){
    if(head==NULL)
    return NULL;
    
    if((head->left && head->left->data==x && head->right && head->right->data==y) 
        ||(head->left && head->left->data==x && head->right && head->right->data==y))
    return true;  // parent contains both x and y as children
    
    return (sameparent(head->left,x,y) || sameparent(head->right,x,y));
}

int depth(tree *head,int value,int d){
    if(head==NULL)
    return 0;
    
    if(head->data==value)
    return d;
    
    return max(depth(head->left,value,d+1),depth(head->right,value,d+1));
}

int main() {
    
    int arr[]={50,30,60,40,10,20,-1};
    int n =sizeof(arr)/sizeof(int);
    int x = 40, y = 20;  
    
    tree *head=maketree(head,arr,n,0);
   
    
    if(!sameparent(head,x,y) && depth(head,x,0)==depth(head,y,0))
    cout<<"Nodes "<<x<<'&'<<y<<" are cousins";
    
    else cout<<"Nodes "<<x<<'&'<<y<<" are NOT cousins";
  
  return 0;
}

Output:

Nodes 40&20 are cousins

The worst-case time complexity is O(n).

That’s it for this tutorial. Hope you understood it.

 

Leave a Reply

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