# 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.*

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.