# Check if two nodes are cousins in a binary tree

In this article, we are going to see how to check whether two nodes are cousin in the binary tree or not?
Submitted by Radib Kar, on August 05, 2020

## Cousins in a Binary Tree

Two nodes are said to be cousins in a binary tree if they belong to the same level but their parent node is different. For example, in the below example,

Figure 1: Example 1

Nodes with value 4 and 6 are cousin here as they are at the same level 2 and their parent is different. Node with value 4 has parent node with value 2 whereas node with value 6 has parent node with value 3. So they are cousins.

But in the below example,

Node with value 4 and node with value 5 is not cousin, since they belong to the same parent.

Solution:

From the definition of a cousin in a tree, we can achieve the solution. The first thing is both the nodes need to be at the same level. So, here comes the level order traversal to determine the levels of the nodes to check. Secondly, we need to check whether the nodes have the same parent or not. For that, we need to store the parents of each node in the hash table for lookup.

So we can design an algorithm like below:

```1)  Do a level order traversal
2)  If at any level a node(one out of those two nodes)   is found Then
Look for the second Node
If the second Node is found in this level, then
Check their parents are the same or not
If their parents are different, then they are cousins
Else they are not cousin
Else if the end of this level reaches without
finding the second node, then
They are not cousin
```

Below is the detailed implementation of the same.

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

// tree node is defined
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int data)
{
val = data;
left = NULL;
right = NULL;
}
};

int sumTree(TreeNode* root)
{
if (!root)
return 0;

//if current node is leaf node return it's sum
if (!root->left && !root->right)
return root->val;

//left subtree sum
int l = sumTree(root->left);

//right subtree sum
int r = sumTree(root->right);

//if root val is equal to sum of left
//subtree + sum of right subtree then return the sum
if (root->val == l + r)
return root->val + l + r;
else //otherwise return INT_MIN
return INT_MIN;
}

bool isSumTree(TreeNode* root)
{
if (!root)
return true;
//if function returns INT_MIN then it's not a sumTree
if (sumTree(root) == INT_MIN)
return false;
return true;
}

int main()
{
//building the tree like example 1
TreeNode* root1 = new TreeNode(10);
root1->left = new TreeNode(3);
root1->right = new TreeNode(4);
root1->left->left = new TreeNode(1);
root1->left->right = new TreeNode(2);

if (isSumTree(root1))
cout << "Tree in example 1 is a Sum Tree\n";
else
cout << "Tree in example 1 is not a Sum Tree\n";

//building the tree-like example 2
TreeNode* root2 = new TreeNode(10);
root2->left = new TreeNode(4);
root2->right = new TreeNode(3);
root2->left->left = new TreeNode(1);
root2->left->right = new TreeNode(2);

if (isSumTree(root2))
cout << "Tree in example 2 is a Sum Tree\n";
else
cout << "Tree in example 2 is not a Sum Tree\n";

return 0;
}
```

Output:

```Tree in example 1 is a Sum Tree
Tree in example 2 is not a Sum Tree
```

If we dry run, for the first example, we will see that at level 2 we will find both. So it will enter the if(flag1 && flag2) statement and since parents of the nodes are different so, it will return true. Whereas, in the second example, since the parent of the nodes are same so it will return false.

There may be the case, where nodes are not at the same level, then, of course, it will return false by entering the if(flag1 || flag2) condition.

What's New

Top Interview Coding Problems/Challenges!

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates