Given a Binary tree/Binary Search tree, find Level which has Maximum Sum of all nodes at that level and print sum.

package tree;

import java.util.LinkedList;
import java.util.Queue;

/*
Given a Binary tree/Binary Search tree, find Level which has Maximum Sum of all nodes at that level and print sum.
Input

     30            ---------> Level 0
   /   \
  20     9         ---------> Level 1
 / \    / \
2   4  1  19       ---------> Level 2
 
output
Level with maximum sum is 1 and sum is 29

Note: 
Solution below assume that sum is different at each level ad not same.
If the sum is same at more then 1 level then it shows the first highest sum encountered level. 
*/

public class FindLevelWithMaximumSum {
 private Node rootNode;

 public static void main(String[] args) {
  new FindLevelWithMaximumSum();
 }

 public FindLevelWithMaximumSum() {
  addNode(rootNode, 30); 
  addNode(rootNode, 20); 
  addNode(rootNode, 9); 
  addNode(rootNode, 2); 
  addNode(rootNode, 4); 
  addNode(rootNode, 1); 
  addNode(rootNode, 19); 
  
  int[] data = findLevelWithMaximumSum(rootNode);
  if(data==null){
   System.out.println("No Nodes Present"); 
  }else{
   System.out.println("Level is "+ data[0]+",Sum is :"+data[1]);
  }
 }
 
 private int[] findLevelWithMaximumSum(Node startNode) {
  if(startNode==null){
   return null;
  }
  
  Queue<Node> q = new LinkedList<Node>();
  q.add(startNode);
  q.add(null);
  
  int maxSum = 0;
  int sum = 0;
  int maxLevel=0;
  int level=0;
  
  while(!q.isEmpty()){
   Node data = q.poll();
   
   if(data == null){
    
    if(!q.isEmpty()){
     q.add(null); 
    }
    
    if(sum>maxSum){
     maxSum = sum;
     maxLevel = level; 
    }
    sum=0;
    level++;
    
   }else{
    if(data.getLeft()!=null)
     q.add(data.getLeft());
    
    if(data.getRight()!=null)
     q.add(data.getRight());
    
    sum = sum + data.getData();
   }
  }
  
  return new int[]{maxLevel, maxSum};
 }

 private void addNode(Node rootNode, int data){

  //First check is there any Nodes present.
  if(rootNode==null){
   // No Nodes are Present, create one and assign it to startNode
   Node temp1=new Node(data);
   this.rootNode=temp1;
  }else{
   //Nodes present, So check the proper position where to add New Node.

   //Checking whether Left child and Right child are present for root Node. 
   if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
    //Left and Right Child exist, Also, we need to add ne Node in Sequential Fashion of Left and Right, 
    //We have to scan all Levels one by one to check a proper place for new Node.
    //Also, we for each and every node we need to check whether Left and Right Exist, 
    //So we need to store them for later Processing that is why we introduced Queue.

    Queue<Node> queue = new LinkedList<Node>();
    queue.add(rootNode);

    while(!queue.isEmpty()){
     Node obj = (Node)queue.poll();
     if(obj.getLeft()!=null && obj.getRight()!=null){
      queue.add(obj.getLeft());
      queue.add(obj.getRight());
     }else if(obj.getLeft()==null){
      Node temp1=new Node(data);
      obj.setLeft(temp1);
      break;
     }else{
      Node temp1=new Node(data);
      obj.setRight(temp1);
      break;
     }
    }

   }else{
    // We reach this condition when either Left or Right is Null, but not sure which side is Null.
    if(rootNode.getLeft()==null){
     Node temp1=new Node(data);
     rootNode.setLeft(temp1);
    }else{
     Node temp1=new Node(data);
     rootNode.setRight(temp1);
    }
   }
  }
 }
}