Cousin nodes in Binary Tree

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.

One Thought on “Cousin nodes in Binary Tree

  1. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation