# 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