In a Binary Tree, Check if two nodes are Cousins

Objective: Given a binary tree and two nodes, Check if they are cousins

Input: A binary tree and two nodes

Cousin Nodes: Cousin nodes are the nodes who are at the same level in the tree and whose parents are siblings.

Example:

Cousin Nodes

Approach:

  • Check the height of both the nodes, if heights are different then return false.
  • Check if both the nodes has the same parent, if yes then return false.
  • else return true.

Complete Code:

public class CheckIiTwoNodesAreCousins {
public boolean areCousins(Node root, Node x, Node y) {
// get the heights of both the nodes and return false if heights ate not
// same
if (getHeight(root, x, 1) != getHeight(root, y, 1))
return false;
else {
// Now check if or not parents are same for both the node, if not ,
// return true
if (sameParents(root, x, y) == false) {
return true;
} else {
return false;
}
}
}
public int getHeight(Node root, Node x, int height) {
if (root == null)
return 0;
if (root == x)
return height;
int level = getHeight(root.left, x, height + 1);
if (level != 0)
return level;
return getHeight(root.right, x, height + 1);
}
public boolean sameParents(Node root, Node x, Node y) {
if (root == null)
return false;
return ((root.left == x && root.right == y)
|| (root.left == y && root.right == x)
|| sameParents(root.left, x, y) || sameParents(root.right, x, y));
}
public static void main(String[] args) throws java.lang.Exception {
Node root = new Node(1);
Node x1 = new Node(2);
Node y1 = new Node(3);
root.left = x1;
root.right = y1;
root.left.left = new Node(4);
root.right.left = new Node(6);
Node x2 = new Node(7);
Node y2 = new Node(9);
root.right.left.left = new Node(8);
root.right.left.right = y2;
root.left.left.left = x2;
CheckIiTwoNodesAreCousins i = new CheckIiTwoNodesAreCousins();
System.out.println("Node " + x1.data + " and Node " + y1.data + " are cousins??? " + i.areCousins(root, x1, y1));
System.out.println("Node " + x2.data + " and Node " + y2.data + " are cousins??? " + i.areCousins(root, x2, y2));
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

Output:

Node 2 and Node 3 are cousins??? false
Node 7 and Node 9 are cousins??? true

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.