Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What do you mean by Level Order Traversal?
4.2.
What are the minimum and maximum height of a binary tree?
4.3.
What is Recursion? Explain Tail Recursion?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if two nodes are cousins in a Binary Tree.

Author Sarthak
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In this Approach, For every level, check if two nodes are present and both are not children of the same Node. For this, We use a queue and perform Level order traversing.

Steps of Algorithm

Step 1. Forming a Queue of Node Pointer type and storing root node.

Step 2. Run a 'while Loop' and it is running until Queue is not empty.

Step 3. Create two variables for 'IsXExist' and 'IsYExist' for tracking whether the nodes are present at the same level or not.

Step 4. Storing pointer in the Queue and checking for its child node whether they have same parents. If yes, return false.

Step 5. If Curr Node has left and right nodes, store them in the Queue.

Step 6. If we found both nodes at a different level, return true.

Step 7. If we traverse all the trees, the nodes are not present at the same level; hence, they return false.

Implementation in C++

#include <iostream>
#include <queue>
using namespace std;
// Structure and formation of node
struct Node
{
    int data;
    Node *left;
    Node *right;


    Node(int val)
    {
        data = val;
        left = right = NULL;
    }
};
// Functions to find whether they are cousins or not
bool IsCousins(Node *root, int x, int y)
{
    if (root == NULL)
        return 0;
    // Initialization of Queue of Node pointer type
    queue<Node *> Queue;
    Queue.push(root);
    while (!Queue.empty())
    {
        int size = Queue.size();
        // Two Variables to find that they are present in same level or not
        bool IsXExist = false;
        bool IsYExist = false;
        for (int i = 1; i <= size; i++)
        {
            Node *curr = Queue.front();
            Queue.pop();


            // Base Case (If any of the node found in the tree)
            if (curr->data == x)
                IsXExist = true;
            if (curr->data == y)
                IsYExist = true;


            if (curr->left != NULL && curr->right != NULL)
            {
                // If given node are children of same parent, return false
                if (curr->left->data == x && curr->right->data == y)
                {
                    return false;
                }
                // If given node are children of same parent, return false
                if (curr->left->data == y && curr->right->data == x)
                {
                    return false;
                }
            }

            // If Left node is present,then push it into the Queue
            if (curr->left)
                Queue.push(curr->left);
            // If Right node is present,then push it into the Queue
            if (curr->right)
                Queue.push(curr->right);
        }
        // If both the node are present at same level,return true.
        if (IsXExist && IsYExist)
            return true;
    }
    // If Tree is traversed ,means the two Nodes are at different Level.
    return false;
}
int main()
{
    // Formation Of Tree
    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);

    int x = root->left->left->data;
    int y = root->right->right->data;
    
    // Functions call having root of Binary Tree, First Node and Second Node
    if (IsCousins(root, x, y))
        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.

Traversing all nodes of the Binary tree takes O(n).

Space complexity

O(d), Where d is the depth of the Tree.

The maximum size of Queue formed in this approach is O(d).

Check out this problem - Mirror A Binary Tree

Must Read Recursion in Data Structure

Frequently Asked Questions

What do you mean by Level Order Traversal?

Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root node etc.

What are the minimum and maximum height of a binary tree?

Consider n number of nodes present in a binary tree, then the maximum height will be n-1, and the minimum height will be log2n.

What is Recursion? Explain Tail Recursion?

Recursion is a process in which a function calls itself again and again directly or indirectly.

Tail Recursion is a type of Recursion in which the function first performs operations on the data and calls itself first after the manipulations is called Tail Recursion.

Conclusion

In this blog, we learned how to Check whether Two Nodes are siblings in a Binary Tree. We have discussed the BruteForce Approach and also seen its time and space complexity. The second approach is quite interesting as it uses a queue and makes our procedure easy by level order traversals of Tree. We hope you will learn something from this and will continue learning.

Suggested problems are Construct a Binary Tree From Preorder and PostorderConstruct a Binary Tree From its Linked-List Representation, and many more.

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingDBMSSystem DesignWeb Development, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! However, if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problemsinterview experiences, and interview bundle.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass