Given the binary Tree and the two nodes say ‘p’ and ‘q’, determine whether the two nodes are cousins of each other or not.
Solution: What are cousin nodes ?
Two nodes are said to be cousins of each other if they are at same level of the Binary Tree and have different parents.
For Example:
A
/ \
B C
/ \ / \
D E F G
Say two node be D and F, result is Cousins.
Say two nodes are F and E, result is Cousins.
Say two nodes are B and C, result is Not Cousins.
The basic approach is to find the height of one of the nodes. Using the found height, check if ‘p’ and ‘q’ are at this height. If ‘p’ and ‘q’ are at same height, then lastly check if they are not children of same parent.
Implementation:
// C Plus Plus Program
#include<stdio.h>
#include<stdlib.h>
// A Binary Tree Node
struct BTNode
{
int data;
BTNode *left, *right;
};
// Creation of a new BT Node
struct BTNode *newBTNode(int info)
{
BTNode *temp = new BTNode();
temp->data = info;
temp->left = temp->right = NULL;
return temp;
}
// Recursive function to check whether Nodes are siblings
int isBTSibling( BTNode *root, BTNode *a, BTNode *b)
{
// Base case
if (root==NULL) return 0;
return ((root->left==a && root->right==b)||
(root->left==b && root->right==a)||
isBTSibling(root->left, a, b)||
isBTSibling(root->right, a, b));
}
// Recursive Function to find level of Node 'ptr' in tree
int BTlevel( BTNode *root, BTNode *ptr, int lev)
{
// base cases
if (root == NULL) return 0;
if (root == ptr) return lev;
// Return level height if Node is present in left subtree
int l = BTlevel(root->left, ptr, lev+1);
if (l != 0) return l;
// Else search in right subtree
return BTlevel(root->right, ptr, lev+1);
}
// Function for cousin checking
int isBTCousin(BTNode *root, BTNode *a, BTNode *b)
{
/* Nodes have to be on the same level in the
binary tree and should not be siblings*/
if ((BTlevel(root,a,1) == BTlevel(root,b,1))
&& !(isBTSibling(root,a,b)))
return 1;
else
return 0;
}
Time Complexity: O(n) as it can do almost three traversals of binary tree.
This can be done in single traversal by using level order traversal. Pushing all values, even the NULL values, in the queue. If two consecutive values pushed in the queue have the passed values return false. Simultaneously have two vars founda and foundb to check if they’re found in the same level. If found at the end of level traversal return true otherwise reset founda and foundb. Repeat process.
int fetchLevel(node *root, node *f, int level) {
if (!root)
return -1;
else if (root->val == f->val)
return level;
else if (root->val val) {
level += 1;
return fetchLevel(root->right,f,level);
} else {
level += 1;
return fetchLevel(root->left,f,level);
}
}
bool areCousinNodes(node *root, node *p, node *q) {
if (p->par == q->par)
return false;
int p_level = 0;
int q_level = 0;
p_level = fetchLevel(root,p,0);
q_level = fetchLevel(root,q,0);
if (p_level != q_level || p_level == -1 || q_level == -1)
return false;
else
return true;
}
Complexity: O(lgn)
we can find the common lowest ancestor of node A and Node B and check whether both are children of the ancestor . if not . check for the height of node A and node B with respect to common ancestor . we both are same . then they are cousins