CareerCup

Will u mind posting any example??

Ex:
a
/ \
b c
/ \ / \
d e f g

Then node(d) if input, output should be f and g. since parent of node(d) is sibling for node(c) whose children are f and g.

You can do this in O(n) time (technically O(log n + n) time which reduces to O(n).
You first check which level of the tree the node is. Store that in a temporary variable.

Then , you do a BST iteration keeping a "count" variable that will be 0 after you have a whole tree level in your queue. You decrement the variable "level" at that ime.

At the begining of the iteration, you check to see if level = 0. If so, you have reached the same level where the node was and you can empty the queue to the list that will be returned as the solution. You just need to make sure you aren't pushing the target node or it's brother to the list (by checking if the parent of that node is the same as the desired node).

public ArrayList<Node> findCousins(Node target)
	{
		if (target == null || root == null)
			return null;
		
		int level = 0;
		Node n = target;
		while (n.parent != null)
		{
			n = n.parent;
			level++;
		}
		
		Queue<Node> q = new LinkedList<Node>();
		
		q.add(root);
		int count = 1;
		
		while (!q.isEmpty())
		{
			if (level == 0)
			{
				ArrayList<Node> cousins = new ArrayList<Node>();
				while (!q.isEmpty())
				{
					Node cousin = q.remove();
					if (cousin.parent != target.parent)
						cousins.add(cousin);
				}
				
				return cousins;
			}
			
			Node current = q.remove();
			
			if (current.left != null)
				q.add(current.left);
			
			if (current.right != null)
				q.add(current.right);
			
			if (--count == 0)
			{
				level--;
				count = q.size();
			}
		}
		
		return null;
	}

Forgot to add my name on the answer above <,<

Guys ,everyone is using queue..No need to use it...just do a preorder traversal and get the level of the node..that is when we are at 1 level we will check whether 2nd level has req. node. and if yes then we check is the req. is left child of current or right and save the opposite child..land then leavinf these two child print the level...
say if root is not the req. child.
int preorder(int child,int *brother,struct node *root,int level)
{
if(root)
{
if(root->left)
{
if(root->left->data)=child
{
if(root->right )
root->right=root->right->data;
}
return level+1;
}

same for right



}


//code to print nodes at k level
if value of node=child or value of node is brother then skip it
else
print


}
}

1. Find grandparent node and get grandparent's children;
2. Remove parent node from grandparent's children;
3. Traverse grandparent's children list and add all children (the cousins we want) of each parent.

public void findCousin(TreeNode *node)
{
	int c1 = 0;
	int c2 = 0;
	boolean flag = False;
	TreeNode *tmp;
	Queue *q = new Queue();
	q.EnQueue(node);
	while(!q.isEmpty() && Flag==False)
	{
		tmp = q.DeQueue();
		if(tmp->left->data == node->data || tmp->right->data == node-->data)
			flag = True;
		else
		{
			q.EnQueue(tmp->left);
			q.EnQueue(tmp->right);
		}
		c2 = q.size();
		if(--c1 == 0)
			c1 = c2;
		else
			-- c1;
	}
	while(!q.isEmpty())
	{
		tmp = q.DeQueue();
		if(c1 > 0)
			-- c1;
			q.EnQueue(tmp->left);
			q.EnQueue(tmp->right);
		else
			System.out.print(tmp->data);
	}
}

My attempt:
using modified BFS and linkedList like a queue.
keep tracking the level number.
always return all nodes in certain level(excluding the target node) if target node is found.

public List<Node> findCousins(Node root,Node src){
if(root==null) return null;
List<Node> q = new LinkedList<Node>();
q.add(root);
int curLevl=0,nodesNoOnCurLevel=1,nodesNoOnNextLevel=0;
boolean isFound=false;
List<Node> cousinsQueue = new LinkedList<Node>();
while(q.size()!=0){
Node curNode = q.remove(0);// acts like dequeue
nodesNoOnCurLevel--; // decrement number of nodes on current level
if(curNode==src){
isFound=true;
}
else
cousinsQueue.add(curNode);
if(curNode.left!=null){
q.add(curNode.left);
nodesNoOnNextLevel++; // increment number of nodes on next level
}
if(curNode.right!=null){
q.add(curNode.right);
nodesNoOnNextLevel++; // increment number of nodes on next level
}
if(nodesNoOnCurLevel==0){
if(isFound==true)
return cousinsQueue;
else{
nodesNoOnCurLevel=nodesNoOnNextLevel;
nodesNoOnNextLevel=0;
curLevl++;
}
}

}
return null;

}

I think a more simple solution is just to go for a DFS and keep a reference on 2 last level ancestors to retrieve cousins as soon as we reach the target node :

public class TreeNode {
    public TreeNode left;
    public TreeNode right;
    public String data;

    public TreeNode(String data) {
        this.data = data;
    }

    public List<TreeNode> findCousins(TreeNode gp, TreeNode p, String data) {
        
        if( this.data.equals(data)) {
            if( gp == null || p == null) {
                return null;
            }
            TreeNode uncle = null;
            if( gp.left == p ) {
                uncle = gp.right;
            } else {
                uncle = gp.left;
            }
            if( uncle == null ) {
                return null;
            }
            
            List<TreeNode> result = new ArrayList<>();
            if( uncle.left != null ) {
                result.add(uncle.left);
            }
            if( uncle.right != null ) {
                result.add(uncle.right);
            }
            if( result.isEmpty() ) {
                return null;
            } else {
                return result;
            }
        } 
        
        if( left != null ) {
            List<TreeNode> leftCousins = left.findCousins( p, this, data);
            if( leftCousins != null ) {
                return leftCousins;
            }
        }
        if( right != null ) {
            List<TreeNode> rightCousins = right.findCousins( p, this, data);
            if( rightCousins != null ) {
                return rightCousins;
            }
        }
        return null;
    }
}

This can be answered by a very simple modification to BFS

Create a Q struct as

struct Q{
 node x;
 int level;
 struct Q *next;
}

BFS(node)
{
 Enq will do as below
 {Q.x=node
 Q.lvl=1}

 while(Q is not empty)
 {
	tmp node=Q.top.x
	tmp lvl=Q.top.level;
	deq(Q)
	if(node->left and right !=elem)
		Enq(node.l,lvl+1)
		Enq(node.r,lvl+1)
	else
		global lvllock=lvl+1;
		break;
 }
}

Q will now contain values which will give us the cousins
for each value in Q seek till lvl+i is less than or equal to lvllock and then
print the values as its cousins til Q is empty

I may be missing something but in a Binary tree, won't a node have maximum of 3 cousins?Those can be found by traversing upto its grandfather (2 operations) and then getting to its 'uncle' (if there is any) and its two children (if there are any). This is a constant time algorithm.