Find level with maximum sum in binary tree - display nodes and sum both

Problem statement:- For a given binary tree, find level with maximum sum and display all nodes at level level.

For above binary tree: maximum sum recorded for 11, 991, 12  and maximum sum is 1014

Algorithm:- Do level order traversal with marking end of level using marker node. We need to store all nodes constituting maximum sum and current nodes, use linked list for it and sum is stored in some variable similarly. Once we traverses all nodes of tree, we have sum and list of nodes giving maximum sum.

1. Enqueue root and marker node into queue. 

2. Dequeue an element from queue and check whether it is a marker node 

    or not. If marker node found, update maxList and maxSum , if maxSum is less than curentSum. If dequeues node is not marker, add node value in sum and enqueue left/right child in queue if exist. 

3. Repeat step 2 until queue is empty.
Time and space complexity:- TC = O(n) and SC = O(n) { 2 list of order n and queue of size n}, n is no of nodes in given binary tree.
Sample code for finding level with maximum sum in binary tree

/* Level with maximum sum of nodes */
public void displayLevelWithMaximumSum(Node root) {
 /* java.util.ArrayDeque */
 Queue<Node> queue = new ArrayDeque<>();
 List<Node> currentLevelList = new LinkedList<>();
 List<Node> maxLevelList = new LinkedList<>();
 int currentlevelSum = 0;
 int maxSum = Integer.MIN_VALUE;
 Node dummy = new Node(Integer.MIN_VALUE);
 if (root != null) {
  queue.add(root);
  queue.add(dummy);
  while (!queue.isEmpty()) {
   /* Dequeue form queue and update sum */
   root = queue.remove();
   /* Dequeued node is marker node and */
   if (root.equals(dummy)) {
    if (maxSum < currentlevelSum) {
     maxSum = currentlevelSum;
     maxLevelList.clear();
     maxLevelList.addAll(currentLevelList);
    }
    currentlevelSum = 0;
    currentLevelList.clear();
    /* Add marker node only when queue has some element */
    if (queue.size() != 0)
     queue.add(dummy);
   }
   /* all nodes of that level is not traversed */
   else {
    currentlevelSum += root.data;
    currentLevelList.add(root);
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }

  }
 }
 System.out.println("Maximum sum value is " + maxSum);
 /* Display maximum level nodes */
 System.out.print("Mximum level nodes are : ");
 for (Node node : maxLevelList)
  System.out.print(node.getData() + " ");
}

Complete sample program- find level with maximum sum in binary tree

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelWithMaximumSum {
/* Level with maximum sum of nodes */
public void displayLevelWithMaximumSum(Node root) {
 /* java.util.ArrayDeque */
 Queue<Node> queue = new ArrayDeque<>();
 List<Node> currentLevelList = new LinkedList<>();
 List<Node> maxLevelList = new LinkedList<>();
 int currentlevelSum = 0;
 int maxSum = Integer.MIN_VALUE;
 Node dummy = new Node(Integer.MIN_VALUE);
 if (root != null) {
  queue.add(root);
  queue.add(dummy);
  while (!queue.isEmpty()) {
   /* Dequeue form queue and update sum */
   root = queue.remove();
   /* Dequeued node is marker node and */
   if (root.equals(dummy)) {
    if (maxSum < currentlevelSum) {
     maxSum = currentlevelSum;
     maxLevelList.clear();
     maxLevelList.addAll(currentLevelList);
    }
    currentlevelSum = 0;
    currentLevelList.clear();
    /* Add marker node only when queue has some element */
    if (queue.size() != 0)
     queue.add(dummy);
   }
   /* all nodes of that level is not traversed */
   else {
    currentlevelSum += root.data;
    currentLevelList.add(root);
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }

  }
 }
 System.out.println("Maximum sum value is " + maxSum);
 /* Display maximum level nodes */
 System.out.print("Mximum level nodes are : ");
 for (Node node : maxLevelList)
  System.out.print(node.getData() + " ");
}

 public static void main(String[] args) {
  LevelWithMaximumSum slo = new LevelWithMaximumSum();
  Node root = slo.new BinaryTree().createTree();
  slo.displayLevelWithMaximumSum(root);
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(198));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(991));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   return root;
  }
 }

 class Node {
  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }

}

=========Sample output========
Maximum sum value is 1014
Mximum level nodes are : 11 991 12
===========================