Introduction
This blog will discuss approaches to check if two nodes are cousins in a Binary Tree. Before Jumping to the solution directly, we will see what a Binary Tree is and what is meant by cousins in a Binary Tree.
A Binary Tree is Data Structure in which every Node has at most two children at max. Binary Tree can be empty as well. The Node at the top(The first Node created) is the Root node. Every Node has two Children named the left child and the right child. The Node from which the child node is created is said to be the child node's parent.
Any two nodes are said to be siblings if they are at the same level in a Binary Tree and are not children of a common parent and In the Binary Tree, all the elements are unique.
Source: Binary Tree
Problem Statement
You are given a Binary Tree and also given two values of two nodes and both are unique in nature. Determine whether the two nodes are cousins of each other.
Sample Example
Input:
In the Input, we have been given a Binary Tree as shown in the above figure, and two nodes having values 4 and 6.
Output:
The given nodes having values 4 and 6 are Cousins of each Other.
As we can clearly see that 4 and 6 are present at the same level and their parents are also different. so, we can say they are cousins.
Brute Force Approach
The approach is straightforward. It is a brute approach and Recursive. We have to traverse through all the nodes and find the Level and Parent of two Node one by one. Now, If levels of two Node are equal and their parents are not the same, they are not cousins.
Initially, the level of the root node is one. When we traverse through the children, we will increase the level by 1. If We find our Node, then return Level of Node. The base case is when our current Node is equal to the given Node, then return level, or current node is NULL, then return 0.
Steps of Algorithm
Step 1. Initialize two Integer variables, 'ParentOfFirstNode' and 'ParentOfSecondNode' as -1, which will store the parent of the given Node at the end.
Step 2. Create a function Find_Level_Of_Node which takes the root node, X, and ParentOfFirstNode (pass by reference).
Step3. First, see if either of the first or second values is equal to the root value of the Binary Tree, then return 0.
Step4. Now, we call our recursive function to find the level of the node. If Node becomes NULL, return 0.
Step5. If Node value is equal to X, then return level.
Step 4. In function Find_Level_Of_Node, Call for the left child with the increased level value. Now If the height is not equal to 0, It means we have found our Node.
Step 5. Call for the right child with the increased value of level.
Step 6. Similarly, For another node, find the level and parent of this Node.
Step 7. If the level is the same and the parent is different, then return true. Otherwise, return false.
Implementation in C++
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
Node(int val)
{
data = val;
left = right = NULL;
}
};
int Find_Level_Of_Node(Node *curr, int &parent, int value, int Level)
{
// Base Case
if (curr == NULL)
return 0;
if (curr->data == value)
return Level;
parent = curr->data;
int left = Find_Level_Of_Node(curr->left, parent, value, Level + 1);
if (left != 0)
return left;
parent = curr->data;
int right = Find_Level_Of_Node(curr->right, parent, value, Level + 1);
return right;
}
int main()
{
struct Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->left->right->right = new Node(15);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->right->left->right = new Node(8);
// First Node Value
int X = root->left->right->data;
// Second Node Value
int Y = root->right->right->data;
if (root->data == X || root->data == Y)
return false;
int ParentofFirstNode = -1;
int LevelofFirstNode = Find_Level_Of_Node(root, ParentofFirstNode, X, 1);
int ParentofSecondNode = -1;
int LevelofSecondNode = Find_Level_Of_Node(root, ParentofSecondNode, Y, 1);
if (ParentofFirstNode != ParentofSecondNode && LevelofFirstNode == LevelofSecondNode)
cout << "The Given Nodes are Cousins of each Other" << endl;
else
cout << "The Given Nodes are Not Cousins of each Other" << endl;
return 0;
}
Output:
The Given Nodes are Cousins of each Other
Complexity Analysis
Time complexity
O(n), where n is the number of nodes in a tree.
Since we are traversing all nodes of the Binary tree. Hence our time complexity is O(n).
Space complexity
O(n), As our function ‘Find_Level_Of_Node’ uses recursion, It uses a stack of maximum size n. Hence our space complexity is O(n).
569+ registered 
