Sum of nodes at each level of binary tree in Java

Topics covered

1. Sum of nodes at each level of binary tree
2. Complete sample program

Problem Statement :- Find sum of nodes at each level of binary tree.

Sum of nodes at each level of binary tree:-    12 41 66 232

Algorithm : Traverse binary tree iteratively in such a way that we keep track of all nodes visited once at given level and keep adding node value in sum variable.Once we traversed all nodes of that level display sum and reset it's value to 0. In order to keep track of end of level nodes we maintain a dummy node and insert for each level.
1. Insert root followed by dummy node in queue.
2. Loop until queue is empty, remove an element from queue.
If removed element is not dummy(else block) - add removed node data in sum and add left/right child in queue.
If removed element is dummy node display sum, reset it to zero and if queue is not empty, add dummy into queue indicating we have reached at end of level and next level will start.

Sample code for finding diameter of binary tree - 

/*Display sum of nodes at each level*/
public void displaySumOfBinaryTreeNodesAtEachLevel(Node root) {
 /* java.util.ArrayDeque */
 Queue<Node> queue = new ArrayDeque<>();
 int sum = 0;
 int level = 1;
 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 or display it */
   root = queue.remove();
   /* Dequeued node is marker node */
   if (root.equals(dummy)) {
    System.out.println("Sum at level " + level + " is " + sum);
    sum = 0;
    level++;
    /* 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 {
    sum += root.data;
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }
  }
 }
}

Complete sample program- find diameter of binary tree

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.Queue;

public class LevelOrderSumOfNodes {
 static int sumRec = 1;
/*Display sum of nodes at each level*/
public void displaySumOfBinaryTreeNodesAtEachLevel(Node root) {
 /* java.util.ArrayDeque */
 Queue<Node> queue = new ArrayDeque<>();
 int sum = 0;
 int level = 1;
 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 or display it */
   root = queue.remove();
   /* Dequeued node is marker node and */
   if (root.equals(dummy)) {
    System.out.println("Sum at level " + level + " is " + sum);
    sum = 0;
    level++;
    /* 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 {
    sum += root.data;
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }

  }
 }
}

 public static void main(String[] args) {
  LevelOrderSumOfNodes slo = new LevelOrderSumOfNodes();
  Node root = slo.new BinaryTree().createTree();
  slo.displaySumOfBinaryTreeNodesAtEachLevel(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(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   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==
Sum at level 1 is 12
Sum at level 2 is 41
Sum at level 3 is 66
Sum at level 4 is 232

================