C++ program to check whether if two nodes are cousins in a binary tree

C++ program to check whether if two nodes are cousins in a binary tree

In this program we are checking if the two given nodes are cousins or not and it can be solved by performing level order traversal. The idea is to use a queue to perform level order traversal, in which each queue element is a pair of node and parent of that node. For each node visited in level order traversal, check if that node is either first given node or second given node. If any node is found store parent of that node. While performing level order traversal, one level is traversed at a time. If both nodes are found in given level, then their parent values are compared to check if they are siblings or not. If one node is found in given level and another is not found, then given nodes are not cousins.

Cousins nodes are the nodes which are same level but with the different parents. Nodes with same parents becomes siblings.

                                         /     \
                                       2        3
                                     /   \     /   \
                                   4     5  6      7

Here we can see 4 and 7 are the cousin nodes

// C++ program to check if two given nodes are cousins or not
using namespace std; 

//creating a new node
struct Node
   int data;
   struct Node *left, *right; 

struct Node* newNode(int item) //to assign space
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); 
    temp->data = item; 
    temp->left = temp->right = NULL; 
    return temp; 

//function template to create binary tree
Node* createTree()
   //creating all nodes needed in the binary tree
   Node* node1 = new Node; 
   node1->data = 1;
   Node* node2 = new Node; 
   node2->data = 2;
   Node* node3 = new Node; 
   node3->data = 3;
   Node* node4 = new Node;
   node4->data = 4;
   Node* node5 = new Node; 
   node5->data = 5;
   Node* node6 = new Node; 
   node6->data = 6;
   Node* node7 = new Node; 
   node7->data = 7;
   //connecting nodes to create a binary tree
   node1->left = node2;
   node1->right = node3;
   node2->left = node4;
   node2->right = node5;
   node3->left = node6;
   node3->right = node7;

   return node1;	//returning the root node as it is connected to every node

bool Cousins(Node* root, Node* a, Node* b) 
    if (root == NULL) 
	return false; 
    Node *parentA= NULL ,*parentB = NULL;   //storing parent of node a and b

    //queue to do level order traversal and every pair is a node and its parent
    queue<pair<Node*, Node*>> q; 
    Node* tmp = newNode(-1); 
    pair<Node*, Node*> data; // To store front datament of queue.  
    q.push(make_pair(root, tmp)); // Push root to queue.
    int levSize; 

    while (!q.empty()) //finding no. of nodes in the current level
          levSize = q.size(); 
	  while (levSize)
	  data = q.front(); 

	  // check if current node is node a or node b or not. 
	  if (data.first->data == a->data)  
		parentA= data.second; 

	  if (data.first->data == b->data) 
		parentB = data.second; 
          // push children of current node to queue. 
	  if (data.first->left) 
		q.push(make_pair(data.first->left, data.first)); 
	  if (data.first->right) 
		q.push(make_pair(data.first->right, data.first)); 
//if we found both the nodes then no need to traverse further if (parentA&& parentB)
  break; } // Check if both nodes are siblings or not. if (parentA&& parentB) return parentA!= parentB; // if one node is found in the current level and other not found then
they are not cousins
if ((parentA&& !parentB) || (parentB && !parentA)) return false; } return false; } int main() { Node* root = createTree(); //creating tree Cousins(root, root->left->left, root->right->right) ?
puts("Yes the given nodes are cousins") :
puts("No the given nodes are not cousins"); return 0; }