Check if two nodes are cousins in a Binary Tree

Last Updated : 23 Jun, 2022

Given the binary Tree and the two nodes say ‘a’ and ‘b’, determine whether the two nodes are cousins of each other or not.
Two nodes are cousins of each other if they are at same level and have different parents.

Example:

     6
   /   \
  3     5
 / \   / \
7   8 1   3
Say two node be 7 and 1, result is TRUE.
Say two nodes are 3 and 5, result is FALSE.
Say two nodes are 7 and 5, result is FALSE.

The idea is to find level of one of the nodes. Using the found level, check if ‘a’ and ‘b’ are at this level. If ‘a’ and ‘b’ are at given level, then finally check if they are not children of same parent.
Following is the implementation of the above approach.

C++

// C++ program to check if two Nodes in a binary tree are
// cousins
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new Binary Tree Node
struct Node* newNode(int item)
{
    struct Node* temp
        = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Recursive function to check if two Nodes are siblings
int isSibling(struct Node* root, struct Node* a,
              struct Node* b)
{
    // Base case
    if (root == NULL)
        return 0;
 
    return ((root->left == a && root->right == b)
            || (root->left == b && root->right == a)
            || isSibling(root->left, a, b)
            || isSibling(root->right, a, b));
}
 
// Recursive function to find level of Node 'ptr' in a
// binary tree
int level(struct Node* root, struct Node* ptr, int lev)
{
    // base cases
    if (root == NULL)
        return 0;
    if (root == ptr)
        return lev;
 
    // Return level if Node is present in left subtree
    int l = level(root->left, ptr, lev + 1);
    if (l != 0)
        return l;
 
    // Else search in right subtree
    return level(root->right, ptr, lev + 1);
}
 
// Returns 1 if a and b are cousins, otherwise 0
int isCousin(struct Node* root, struct Node* a, struct Node* b)
{
    // 1. The two Nodes should be on the same level in the
    // binary tree.
    // 2. The two Nodes should not be siblings (means that
    // they should
    // not have the same parent Node).
    if ((level(root, a, 1) == level(root, b, 1)) && !(isSibling(root, a, b)))
        return 1;
    else
        return 0;
}
 
// Driver Program to test above functions
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->right = newNode(15);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
 
    struct Node *Node1, *Node2;
    Node1 = root->left->left;
    Node2 = root->right->right;
 
    if (isCousin(root, Node1, Node2))
        printf("Yes\n");
    else
        printf("No\n");
 
    return 0;
}
 
// This code is contributed by ajaymakwana

C

// C program to check if two Nodes in a binary tree are cousins
#include <stdio.h>
#include <stdlib.h>
 
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new Binary Tree Node
struct Node *newNode(int item)
{
    struct Node *temp =  (struct Node *)malloc(sizeof(struct Node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Recursive function to check if two Nodes are siblings
int isSibling(struct Node *root, struct Node *a, struct Node *b)
{
    // Base case
    if (root==NULL)  return 0;
 
    return ((root->left==a && root->right==b)||
            (root->left==b && root->right==a)||
            isSibling(root->left, a, b)||
            isSibling(root->right, a, b));
}
 
// Recursive function to find level of Node 'ptr' in a binary tree
int level(struct Node *root, struct Node *ptr, int lev)
{
    // base cases
    if (root == NULL) return 0;
    if (root == ptr)  return lev;
 
    // Return level if Node is present in left subtree
    int l = level(root->left, ptr, lev+1);
    if (l != 0)  return l;
 
    // Else search in right subtree
    return level(root->right, ptr, lev+1);
}
 
 
// Returns 1 if a and b are cousins, otherwise 0
int isCousin(struct Node *root, struct Node *a, struct Node *b)
{
    //1. The two Nodes should be on the same level in the binary tree.
    //2. The two Nodes should not be siblings (means that they should
    // not have the same parent Node).
    if ((level(root,a,1) == level(root,b,1)) && !(isSibling(root,a,b)))
        return 1;
    else return 0;
}
 
// Driver Program to test above functions
int main()
{
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->right = newNode(15);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
 
    struct Node *Node1,*Node2;
    Node1 = root->left->left;
    Node2 = root->right->right;
 
    isCousin(root,Node1,Node2)? puts("Yes"): puts("No");
 
    return 0;
}

Java

// Java program to check if two binary tree are cousins
class Node
{
    int data;
    Node left, right;
 
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree
{
    Node root;
 
    // Recursive function to check if two Nodes are
    // siblings
    boolean isSibling(Node node, Node a, Node b)
    {
        // Base case
        if (node == null)
            return false;
 
        return ((node.left == a && node.right == b) ||
                (node.left == b && node.right == a) ||
                isSibling(node.left, a, b) ||
                isSibling(node.right, a, b));
    }
 
    // Recursive function to find level of Node 'ptr' in
    // a binary tree
    int level(Node node, Node ptr, int lev)
    {
        // base cases
        if (node == null)
            return 0;
 
        if (node == ptr)
            return lev;
 
        // Return level if Node is present in left subtree
        int l = level(node.left, ptr, lev + 1);
        if (l != 0)
            return l;
 
        // Else search in right subtree
        return level(node.right, ptr, lev + 1);
    }
 
    // Returns 1 if a and b are cousins, otherwise 0
    boolean isCousin(Node node, Node a, Node b)
    {
        // 1. The two Nodes should be on the same level
        //       in the binary tree.
        // 2. The two Nodes should not be siblings (means
        //    that they should not have the same parent
        //    Node).
        return ((level(node, a, 1) == level(node, b, 1)) &&
                (!isSibling(node, a, b)));
    }
 
    //Driver program to test above functions
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.left.right.right = new Node(15);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.right.left.right = new Node(8);
 
        Node Node1, Node2;
        Node1 = tree.root.left.left;
        Node2 = tree.root.right.right;
        if (tree.isCousin(tree.root, Node1, Node2))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to check if two nodes in a binary 
# tree are cousins
 
# A Binary Tree Node
class Node:
     
    # Constructor to create a new Binary Tree
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
def isSibling(root, a , b):
 
    # Base Case
    if root is None:
        return 0
 
    return ((root.left == a and root.right ==b) or
            (root.left == b and root.right == a)or
            isSibling(root.left, a, b) or
            isSibling(root.right, a, b))
 
# Recursive function to find level of Node 'ptr' in 
# a binary tree
def level(root, ptr, lev):
     
    # Base Case 
    if root is None :
        return 0
    if root == ptr: 
        return lev
 
    # Return level if Node is present in left subtree
    l = level(root.left, ptr, lev+1)
    if l != 0:
        return l
 
    # Else search in right subtree
    return level(root.right, ptr, lev+1)
 
 
# Returns 1 if a and b are cousins, otherwise 0
def isCousin(root,a, b):
     
    # 1. The two nodes should be on the same level in 
    # the binary tree
    # The two nodes should not be siblings(means that 
    # they should not have the same parent node
 
    if ((level(root,a,1) == level(root, b, 1)) and
            not (isSibling(root, a, b))):
        return 1
    else:
        return 0
 
 
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.right = Node(15)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
 
node1 = root.left.right
node2 = root.right.right 
 
print ("Yes" if isCousin(root, node1, node2) == 1 else "No")
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to check if two binary 
// tree are cousins 
using System;
 
public class Node
{
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG
{
public Node root;
 
// Recursive function to check if 
// two Nodes are siblings 
public virtual bool isSibling(Node node, 
                              Node a, Node b)
{
    // Base case 
    if (node == null)
    {
        return false;
    }
 
    return ((node.left == a && node.right == b) || 
            (node.left == b && node.right == a) || 
                     isSibling(node.left, a, b) || 
                     isSibling(node.right, a, b));
}
 
// Recursive function to find level 
// of Node 'ptr' in a binary tree 
public virtual int level(Node node, Node ptr, int lev)
{
    // base cases 
    if (node == null)
    {
        return 0;
    }
 
    if (node == ptr)
    {
        return lev;
    }
 
    // Return level if Node is present 
    // in left subtree 
    int l = level(node.left, ptr, lev + 1);
    if (l != 0)
    {
        return l;
    }
 
    // Else search in right subtree 
    return level(node.right, ptr, lev + 1);
}
 
// Returns 1 if a and b are cousins, 
// otherwise 0 
public virtual bool isCousin(Node node, 
                             Node a, Node b)
{
    // 1. The two Nodes should be on the 
    //      same level in the binary tree. 
    // 2. The two Nodes should not be siblings 
    // (means that they should not have the 
    //  same parent Node). 
    return ((level(node, a, 1) == level(node, b, 1)) && 
                            (!isSibling(node, a, b)));
}
 
// Driver Code
public static void Main(string[] args)
{
    GFG tree = new GFG();
    tree.root = new Node(1);
    tree.root.left = new Node(2);
    tree.root.right = new Node(3);
    tree.root.left.left = new Node(4);
    tree.root.left.right = new Node(5);
    tree.root.left.right.right = new Node(15);
    tree.root.right.left = new Node(6);
    tree.root.right.right = new Node(7);
    tree.root.right.left.right = new Node(8);
 
    Node Node1, Node2;
    Node1 = tree.root.left.left;
    Node2 = tree.root.right.right;
    if (tree.isCousin(tree.root, Node1, Node2))
    {
        Console.WriteLine("Yes");
    }
    else
    {
        Console.WriteLine("No");
    }
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
      // JavaScript program to check if two binary
      // tree are cousins
      class Node {
        constructor(item) {
          this.data = item;
          this.left = null;
          this.right = null;
        }
      }
 
      class GFG {
        constructor() {
          this.root = null;
        }
 
        // Recursive function to check if
        // two Nodes are siblings
        isSibling(node, a, b) {
          // Base case
          if (node == null) {
            return false;
          }
 
          return (
            (node.left == a && node.right == b) ||
            (node.left == b && node.right == a) ||
            this.isSibling(node.left, a, b) ||
            this.isSibling(node.right, a, b)
          );
        }
 
        // Recursive function to find level
        // of Node 'ptr' in a binary tree
        level(node, ptr, lev) {
          // base cases
          if (node == null) {
            return 0;
          }
 
          if (node == ptr) {
            return lev;
          }
 
          // Return level if Node is present
          // in left subtree
          var l = this.level(node.left, ptr, lev + 1);
          if (l != 0) {
            return l;
          }
 
          // Else search in right subtree
          return this.level(node.right, ptr, lev + 1);
        }
 
        // Returns 1 if a and b are cousins,
        // otherwise 0
        isCousin(node, a, b) 
        {
         
          // 1. The two Nodes should be on the
          //     same level in the binary tree.
          // 2. The two Nodes should not be siblings
          // (means that they should not have the
          // same parent Node).
          return (
            this.level(node, a, 1) == this.level(node, b, 1) &&
            !this.isSibling(node, a, b)
          );
        }
      }
 
      // Driver Code
      var tree = new GFG();
      tree.root = new Node(1);
      tree.root.left = new Node(2);
      tree.root.right = new Node(3);
      tree.root.left.left = new Node(4);
      tree.root.left.right = new Node(5);
      tree.root.left.right.right = new Node(15);
      tree.root.right.left = new Node(6);
      tree.root.right.right = new Node(7);
      tree.root.right.left.right = new Node(8);
 
      var Node1, Node2;
      Node1 = tree.root.left.left;
      Node2 = tree.root.right.right;
      if (tree.isCousin(tree.root, Node1, Node2)) {
        document.write("Yes");
      } else {
        document.write("No");
      }
       
      // This code is contributed by rdtank.
    </script>

Output

Yes

Time Complexity of the above solution is O(n) as it does at most three traversals of binary tree.
Space complexity: O(n) for call stack since using recursion

Check if two nodes are cousins in a Binary Tree | Set-2

GeeksforGeeks

Improve

Previous Article

Check if a given Binary Tree is Sum Tree

Check if removing an edge can divide a Binary Tree in two halves

Similar Reads

Check if two nodes are cousins in a Binary Tree | Set-2

Given a binary tree and the two nodes say 'a' and 'b', determine whether two given nodes are cousins of each other or not.Two nodes are cousins of each other if they are at same level and have different parents. Example: 6 / \ 3 5 / \ / \ 7 8 1 3 Say two node be 7 and 1, result is TRUE. Say two nodes are 3 and 5, result is FALSE. Say two nodes are

Sum of cousins of a given node in a Binary Tree

Given a binary tree and data value of a node. The task is to find the sum of cousin nodes of given node. If given node has no cousins then return -1. Note: It is given that all nodes have distinct values and the given node exists in the tree. Examples: Input: 1 / \ 3 7 / \ / \ 6 5 4 13 / / \ 10 17 15 key = 13 Output: 11 Cousin nodes are 5 and 6 whi

Print cousins of a given node in Binary Tree | Single Traversal

Given a binary tree and a node, print all cousins of given node. Note that siblings should not be printed. Examples: Input : root of below tree 1 / \ 2 3 / \ / \ 4 5 6 7 and pointer to a node say 5. Output : 6, 7Recommended PracticeCousins of a given nodeTry It! Note that it is the same problem as given at Print cousins of a given node in Binary Tr

Print cousins of a given node in Binary Tree

Given a binary tree and a node, print all cousins of given node. Note that siblings should not be printed.Example: Input : root of below tree 1 / \ 2 3 / \ / \ 4 5 6 7 and pointer to a node say 5. Output : 6, 7 The idea to first find level of given node using the approach discussed here. Once we have found level, we can print all nodes at a given l

Find the cousins of a given element in an N-ary tree

Given an N-array tree root and an integer K, the task is to print all the cousins of node K. Note: Two nodes are considered to be cousins if they have the same depth (are on the same level) and have different parents. Examples: Consider the below tree: Input: K = 39Output: 88 98 61 74 17 72 19 Input: K = 17Output: 88 98 61 74 39 Input: K = 90Output

Check if all nodes of the Binary Tree can be represented as sum of two primes

Given a binary tree of N nodes with odd value. The task is to check whether all the nodes of the tree can be represented as the sum of the two prime numbers or not. Examples: Input: Output: Yes Explanation: All the nodes in the tree can be represented as the sum of two prime numbers as: 9 = 2 + 7 15 = 2 +13 7 = 2 + 5 19 = 2 + 17 25 = 2 + 23 13 = 11

Check if two nodes in a Binary Tree are siblings

Given a binary tree and two nodes, the task is to check if the nodes are siblings of each other or not. Two nodes are said to be siblings if they are present at the same level, and their parents are the same. Examples: Input : 1 / \ 2 3 / \ / \ 4 5 6 7First node is 4 and Second node is 6.Output : No, they are not siblings.Input : 1 / \ 5 6 / / \ 7

Count the nodes of the tree which make a pangram when concatenated with the sub-tree nodes

Given a tree, and the weights (in the form of strings) of all the nodes, the task is to count the nodes whose weighted string when concatenated with the strings of the sub-tree nodes becomes a pangram. Pangram: A pangram is a sentence containing every letter of the English Alphabet. Examples: Input: Output: 1 Only the weighted string of sub-tree of

Sum of nodes in a binary tree having only the left child nodes

Given a binary tree, the task is to find the sum of binary tree nodes having only the left child nodes. Example: Input: 8 / \ 3 7 / \ / 5 6 0 / / 1 2Output: 18 Explanation: Nodes with values 5, 6, and 7 are the ones that have only the left child nodes Input: 2 / \ 3 1 / / 5 6Output: 4 Approach: The given problem can be solved by traversing the bina

Count of nodes in a binary tree having their nodes in range [L, R]

Given a Binary Tree consisting of N nodes and two positive integers L and R, the task is to find the count of nodes having their value in the range [L, R]. Examples: Input: Tree in the image below, L = 4, R = 15 Output: 2Explanation: The nodes in the given Tree that lies in the range [4, 15] are {5, 10}. Input: Tree in the image below, L = 8, R = 2

Article Tags :

Practice Tags :