Find the rightmost cousin of a binary tree

Find the rightmost cousin of a binary tree - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a node in a binary tree. Find the rightmost cousin of the give node.

                             1
                          /      \
                         2        3
                      /         /   \
                     4         5     6
                       \           /
                        7         8

Rightmost cousin of 4 is 6, right most cousin of 7 is 8 and so on.
we are in the target level and all the nodes in the queue are in the same level hence are cousins and the last node is the right most cousin.

public static class BTNode{
 int key;
 int val;
 BTNode left;
 BTNode right;
 BTNode next;
 
 public BTNode(int key){
  this.key = key;
 }

 @Override
 public String toString() {
  return key+"";
 }
}

public static BTNode rightMostCousin(BTNode root, int targetKey){
 LinkedList<BTNode> q = new LinkedList<BTNode>();
 
 int count = 0;
 q.add(root); 
 count++;
 boolean targetLevel = false;
 
 while(!q.isEmpty())
 {
  BTNode node = q.remove(); 
  count--;
  if(node.key == targetKey)
   targetLevel = true;   
  
  if(node.left != null) q.add(node.left);
  if(node.right != null) q.add(node.right);

  if(count == 0){   
   count = q.size();
   if(targetLevel){
    if(node.key != targetKey)
     return node;
    else return null;
   }
  }
 }
 
 return null;
}

Slight variation of this program can lead us to solution to other problems such as:

1. Find all the cousins of a binary tree node
2. Print a binary tree in level order
3. Connect level order sibling
4. Find level of a node, etc.

public static void printLevelOrder(BTNode root){
 Queue<BTNode> queue = new LinkedList<test.BTNode>();
 queue.offer(root);
 
 BTNode node = null;
 int count = 1;
 while(!queue.isEmpty()){
  node = queue.poll();
  count--;
  
  System.out.print(node.key+" ");
  if(node.left != null){
   queue.offer(node.left);
  }
  if(node.right != null){
   queue.offer(node.right);
  }
  
  if(count == 0){
   System.out.println("");
   count = queue.size();
  }
 }
}

public static void connectLevelOrder(BTNode root){
 Queue<BTNode> queue = new LinkedList<test.BTNode>();
 queue.offer(root);
 
 BTNode node = null;
 int count = 1;
 while(!queue.isEmpty()){
  if(node == null){
   node = queue.poll();
   node.next = null;
  }
  else{
   node.next = queue.poll();
   node = node.next;
  }
  count--;
  
  System.out.print(node.key+" ");
  if(node.left != null){
   queue.offer(node.left);
  }
  if(node.right != null){
   queue.offer(node.right);
  }
  
  if(count == 0){
   node = null;
   System.out.println("");
   count = queue.size();
  }
 }
}

Read full article from Find the rightmost cousin of a binary tree - Algorithms and Problem SolvingAlgorithms and Problem Solving