In a binary tree two nodes are cousins if they are on same level and they have different parent.
For this in a binary search tree, I associated with every key a level using a tree map and also associated with every key a parent using a tree map. Then i invoke BFS on root which sets the levels of various keys.
But my isCousins function is giving false even for nodes that are cousins.For example in the binary tree i have created in my code, 12 and 50 are cousins but still it is printing false.
Here is my source code.
import java.util.*;
class BST
{
Node root;
LinkedList<Node> q=new LinkedList<Node>();
TreeMap<Integer,Integer> level=new TreeMap<Integer,Integer>();
TreeMap<Integer,Node> parent=new TreeMap<Integer,Node>();
Node insert(Node x,int key)
{
if(x==null)
{
parent.put(key,null);
return new Node(key,null,null,null);
}
else if(x.key<key)
{
x.right=insert(x.right,key);
x.right.parent=x;
parent.put(key,x.right.parent);
return x;
}
else if(x.key>key)
{
x.left=insert(x.left,key);
x.left.parent=x;
parent.put(key,x.left.parent);
return x;
}
else { x.key=key; return x;}
}
public void BFS(Node r)
{
if(r==null)
return;
if(r.parent==null)
level.put(r.key,0);
else level.put(r.key,level.get(r.parent.key)+1);
q.add(r);
while(q.size()!=0)
{
Node n=q.poll();
BFS(n.left);
BFS(n.right);
}
}
public boolean isCousins(int a,int b)
{
BFS(root);
if(level.get(a)==level.get(b)&&parent.get(a)!=parent.get(b))
return true;
else return false;
}
public static void main(String []args)
{
BST tree1=new BST();
tree1.root=null;
tree1.root=tree1.insert(tree1.root,15);
tree1.root=tree1.insert(tree1.root,66);
tree1.root=tree1.insert(tree1.root,5);
tree1.root=tree1.insert(tree1.root,3);
tree1.root=tree1.insert(tree1.root,12);
tree1.root=tree1.insert(tree1.root,75);
tree1.root=tree1.insert(tree1.root,50);
System.out.println(tree1.isCousins(12,50));
}
}
class Node
{
Node left,right,parent;
int key;
int level;
Node(int k,Node l,Node r,Node p)
{
key=k;
left=l;
right=r;
parent=p;
}
}
Courtesy of Patrick Murphy, wrong output was coming due to small mistake which i easily corrected using following contion:
if(parent.get(key)==null)
The correct code is: