Given two nodes in a binary tree, check if they are cousins.
Given the binary Tree and the two nodes say ‘p’ and ‘q’, determine whether the two nodes are cousins of each other or not.
Two nodes are cousins if,
- They are not siblings (Children of same parent).
- They are on the same level.
Lets see few example for better understanding on when two nodes are said to be cousin of each other in Binary Tree.
Algorithm
There are 2 ways to check whether 2 nodes are cousins of each other in Binary Tree.
1. Iterative approach.
2. Recursive approach.
Either we go through Recursive or Iterative approach, For identifying nodes are cousins of each other, we need to go through below 2 steps.
STEP 1:
Nodes should not have same parent (otherwise they will be siblings and not cousins)
For checking this, we will traverse the Tree and for each node,
we will see whether given 2 nodes are child of current node,
If YES, then they are not cousins. return false.
STEP 2:
Nodes should be at same Level (otherwise they are not cousins)
For identifying whether two nodes belong to same level, we will identify whether Height of both nodes from Root is same,
If NO, then they are not cousins. return false.
There is separate detailed post on how to find Level of Node in Binary Tree.
Get Level of node in Binary Tree in Java.
Algorithm:
In Recursive approach, we will first find level/height of both nodes and if they are same then we will go for checking whether both nodes have same parent or different parent.
In Iterative approach, we will go level by level and see if both nodes belong to same parent or different parent,
And at the end of each level, we identify whether both nodes belong to same Level.
For detailed understanding, I recommend to go through this post, It explains in detailed on how to find level of node in Binary tree Iteratively:
Get Level of node in Binary Tree in Java.
Java Program to Check whether two nodes are cousins in Binary Tree Recursive Approach
package javabypatel.tree;
import java.util.LinkedList;
import java.util.Queue;
/*
10
/ \
5 20
/ \ / \
3 8 15 25
/
7
*/
public class CheckTwoNodesAreCousinsInBinaryTree {
public static void main(String[] args) {
Node rootNode=null;
rootNode = addNode(rootNode, 10, true);
rootNode = addNode(rootNode, 5, true);
rootNode = addNode(rootNode, 20, true);
rootNode = addNode(rootNode, 3, true);
rootNode = addNode(rootNode, 8, true);
rootNode = addNode(rootNode, 7, true);
rootNode = addNode(rootNode, 15, true);
rootNode = addNode(rootNode, 25, true);
int a = 15;
int b = 8;
System.out.println(checkCousinRecursive(rootNode, a, b));
}
private static boolean checkCousinRecursive(Node start, int node1Data, int node2Data){
int levelNode1 = findLevel(start, node1Data, 0);
int levelNode2 = findLevel(start, node2Data, 0);
if(levelNode1 == -1 || levelNode2 == -1){
return false;
}
if(levelNode1 != levelNode2){
return false;
}
return isCousin(start, node1Data, node2Data);
}
private static boolean isCousin(Node startNode, int node1Data, int node2Data){
if(startNode==null){
return false;
}
if(startNode.getLeft()!=null && startNode.getRight()!=null){
if( (startNode.getLeft().getData() == node1Data && startNode.getRight().getData() == node2Data) ||
(startNode.getLeft().getData() == node2Data && startNode.getRight().getData() == node1Data) ){
return false; //if both node have same parent then they are sibling and not cousin
}
}
boolean left = isCousin(startNode.getLeft(), node1Data, node2Data);
if(!left){
return false;
}
boolean right = isCousin(startNode.getRight(), node1Data, node2Data);
if(!right){
return false;
}
return true;
}
private static int findLevel(Node startNode, int nodeData, int level){
if(startNode==null){
return 0;
}
if(startNode.getData() == nodeData){
return level;
}
int left = findLevel(startNode.getLeft(), nodeData, level+1);
if(left != 0) return left;
int right = findLevel(startNode.getRight(), nodeData, level+1);
if(right != 0) return right;
return 0;
}
private static Node addNode(Node rootNode, int i, boolean isRootNode) {
if(rootNode==null){
return new Node(i);
}else{
if(i > rootNode.getData()){
if(isRootNode){
Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
rootNode.setRight(nodeToAdd);
}else{
Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
rootNode.setLeft(nodeToAdd);
}
}else{
if(isRootNode){
Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
rootNode.setLeft(nodeToAdd);
}else{
Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
rootNode.setRight(nodeToAdd);
}
}
}
return rootNode;
}
}
Java Program to Check whether two nodes are cousins in Binary Tree Iterative Approach
package javabypatel.tree;
import java.util.LinkedList;
import java.util.Queue;
/*
10
/ \
5 20
/ \ / \
3 8 15 25
/
7
*/
public class CheckTwoNodesAreCousinsInBinaryTree {
public static void main(String[] args) {
Node rootNode=null;
rootNode = addNode(rootNode, 10, true);
rootNode = addNode(rootNode, 5, true);
rootNode = addNode(rootNode, 20, true);
rootNode = addNode(rootNode, 3, true);
rootNode = addNode(rootNode, 8, true);
rootNode = addNode(rootNode, 7, true);
rootNode = addNode(rootNode, 15, true);
rootNode = addNode(rootNode, 25, true);
int a = 15;
int b = 8;
System.out.println(checkCousin(rootNode, a, b));
}
private static boolean checkCousin(Node start, int node1Data, int node2Data){
if(start == null){
return false;
}
boolean node1Found = false;
boolean node2Found = false;
int node1Level = -1;
int node2Level = -1;
int currentLevel = 1;
Queue<Node> q = new LinkedList<Node>();
q.add(start);
q.add(null);
while(q!=null){
Node node = q.poll();
if(node==null){
//End of current node level
//If one of node is found and other node is not found, in that case return false
if(node1Found){
if(!node2Found){
return false;
}
}
if(node2Found){
if(!node1Found){
return false;
}
}
//Check both nodes are found, if yes, then see they both are found at same level,
//if yes then return true else false.
if(node1Found && node2Found){
if(node1Level == node2Level){
return true;
}else{
return false;
}
}
//Check if there is any further level to process
if(q.peek()!=null){
currentLevel++;
q.add(null); //Marking end of next level.
}
}else if(node.getLeft()!=null && node.getRight()!=null){
//Check if node1 and node2 is child of current node, if yes, then they are not cousin and is sibling.
if(node.getLeft().getData() == node1Data && node.getRight().getData() == node2Data ||
node.getLeft().getData() == node2Data && node.getRight().getData() == node1Data ){
return false;
}
//Check we may able to found at least one node.
//node1 may be at left side or right side
if(node.getLeft().getData() == node1Data || node.getRight().getData() == node1Data){
node1Found = true;
node1Level = currentLevel;
}
//node2 may be at left side or right side
if(node.getLeft().getData() == node2Data || node.getRight().getData() == node2Data){
node2Found = true;
node2Level = currentLevel;
}
if(node.getLeft()!=null)
q.add(node.getLeft());
if(node.getRight()!=null)
q.add(node.getRight());
}
}
return false;
}
private static Node addNode(Node rootNode, int i, boolean isRootNode) {
if(rootNode==null){
return new Node(i);
}else{
if(i > rootNode.getData()){
if(isRootNode){
Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
rootNode.setRight(nodeToAdd);
}else{
Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
rootNode.setLeft(nodeToAdd);
}
}else{
if(isRootNode){
Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
rootNode.setLeft(nodeToAdd);
}else{
Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
rootNode.setRight(nodeToAdd);
}
}
}
return rootNode;
}
}
You may also like to see
Top Binary tree interview questions in Java
Find Kth SMALLEST element in BST(Binary Search Tree)
Check whether Binary Tree is foldable or not.
Check if two nodes are cousins in a Binary Tree.
Get Level/Height of node in binary tree
Print nodes at K distance from Leaf node in Binary tree.
Construct a Binary Tree from In-order and Post-order traversals.
Print Nodes in Top View of Binary Tree.
Zig Zag Traversal of Binary Tree.
Print nodes at K distance from Leaf node in Binary tree.
Find Kth largest element in BST(Binary Search Tree)
Serialize and Deserialize a Binary Tree
Rotate matrix by 90 degree
Print Matrix Diagonally OR Diagonal order of Matrix.
Count number of Bits to be flipped to convert A to B
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment