Binary Tree: Given a binary tree and two nodes, check if they are cousins

Problem Statement:

Given a binary tree and two nodes, check if they are cousins

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

node 1 = 2, node 2 = 11

Output:

True

Solution Explanation:

We will use BFS to solve the problem.

We will check if the nodes belong to the same level.

And we will also check if they do not belong to same parent.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

bool solution (Node* root, int x, int y) 
{
    queue<Node*>q;
    q.push(root);

    while(!q.empty())
    {
        int n=q.size();

        // use l1 and l2 to track the the level of the 2 nodex
        bool l1 = false, l2 = false;

        for(int i=0; i<n; i++)
        {
            Node *tmp = q.front();
            q.pop();

            if(tmp->data == x) 
            	l1 = true;

            if(tmp->data == y) 
            	l2 = true;
            
            // check if the parents are same
            if(tmp->left && tmp->right)
            {
            	if((tmp->left->data==x && tmp->right->data==y)|| (tmp->left->data==y && tmp->right->data==x))

                return false;
            }

            //else add children to the queue for next level processing
            if(tmp->left)
                q.push(tmp->left);
            if(tmp->right)
                q.push(tmp->right);
        }
      
      	// both are found at the same lelvel
      	// and are cousins return true

        if(l1 && l2)
            return true;
    }
    
    return false;
}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);
    
    cout << solution(root, 2, 14);
    return 0;
}

Output

1