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

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

Zigzag level order traversal of binary tree in Java

Problem statement:- Traverse given binary tree alternatively left to right and right to left.In following diagram, LtoR represents : visit nodes from left to right in that level, similarly RtoL : visit nodes from right to left in that level. Read level order traversal of binary tree.

Zigzag level order traversal of above binary tree :- 12 18 23 11 43 12 27 98 32 78 56 87 29

Algorithm:- In order to solve this problem, we can use two stacks,say currentLevelStack(CLS) and nextLevelStack(NLS). While traversing, we need to keep track of each level and for each level we use alternate stack.

1. Push root node into CLS and loop until this stack is not empty.
2. Pop an element from CLS and display, check whether we are traversing from left to right/right to left.
   If left2right - push nodes into NLS left child followed by right child, otherwise right child followed by left child. 
3. Do check for empty condition of CLS,if empty - it means we have traversed all nodes of that level. Swap references of CLS and NLS and toggle boolean flag left2right. 
4. Repeat 2 and 3 until CLS is not empty and display nodes. 

Sample code for zigzag level order traversal of binary tree in Java

/* Zigzag traversal of binary tree - L2R and R2L alternatively */
public void zigzagLevelOrderTraversal(Node root) {
 /* java.util.stack */
 Stack<Node> currentLevelStack = new Stack<>();
 Stack<Node> nextLevelStack = new Stack<>();
 /* if true, current stack is used, else next stack */
 boolean left2right = true;
 if (root != null) {
  currentLevelStack.push(root);
  while (!currentLevelStack.isEmpty()) {
   /* pop node from stack */
   root = currentLevelStack.pop();
   System.out.print(root.data + " ");
   Node lc = root.leftChild;
   Node rc = root.rightChild;
   if (left2right) {
    /* left child followed by right child */
    if (lc != null) {
     nextLevelStack.push(lc);
    }
    if (rc != null) {
     nextLevelStack.push(rc);
    }
   } else {
    /* Right child followed by left child */
    if (rc != null) {
     nextLevelStack.push(rc);
    }
    if (lc != null) {
     nextLevelStack.push(lc);
    }
   }
   /*
    * Change order of traversal(L2R or R2L) and swap reference of
    * current and next stack
    */
   if (currentLevelStack.isEmpty()) {
    left2right = !left2right;
    /* swap reference of current and next stack */
    Stack<Node> temp = currentLevelStack;
    currentLevelStack = nextLevelStack;
    nextLevelStack = temp;

   }
  }
 }
}

Explanation:- Extra space for two stack incurred (space complexity is order of O(n))and a boolean flag is used to keep track of we are traversing from left to right or right to left.As discussed in above, loop until currentLevelStack(CLS) is not empty and push all child nodes in nextLevelStack(NLS). Once stack is empty change the references of CLS and NLS (in order to avoid moving all elements from NLS to CLS). Boolean flag is also toggled to change direction of traversal in next level.

Complete sample program zigzag level order traversal of binary tree in Java 

package com.devinline.trees;

import java.util.Stack;

public class ZigzagBinaryTreeTraversal {
/* Zigzag traversal of binary tree - L2R and R2L alternatively */
public void zigzagLevelOrderTraversal(Node root) {
 /* java.util.stack */
 Stack<Node> currentLevelStack = new Stack<>();
 Stack<Node> nextLevelStack = new Stack<>();
 /* if true, current stack is used, else next stack */
 boolean left2right = true;
 if (root != null) {
  currentLevelStack.push(root);
  while (!currentLevelStack.isEmpty()) {
   /* pop node from stack */
   root = currentLevelStack.pop();
   System.out.print(root.data + " ");
   Node lc = root.leftChild;
   Node rc = root.rightChild;
   if (left2right) {
    /* left child followed by right child */
    if (lc != null) {
     nextLevelStack.push(lc);
    }
    if (rc != null) {
     nextLevelStack.push(rc);
    }
   } else {
    /* Right child followed by left child */
    if (rc != null) {
     nextLevelStack.push(rc);
    }
    if (lc != null) {
     nextLevelStack.push(lc);
    }
   }
   /*
    * Change order of traversal(L2R or R2L) and swap reference of
    * current and next stack
    */
   if (currentLevelStack.isEmpty()) {
    left2right = !left2right;
    /* swap reference of current and next stack */
    Stack<Node> temp = currentLevelStack;
    currentLevelStack = nextLevelStack;
    nextLevelStack = temp;

   }
  }
 }
}

 public static void main(String[] args) {
  ZigzagBinaryTreeTraversal zlo = new ZigzagBinaryTreeTraversal();
  Node root = zlo.new BinaryTree().createTree();
  System.out.print("Level order traversal in zigzag order: ");
  zlo.zigzagLevelOrderTraversal(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().setRightChild(new Node(27));
   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));
   root.getRightChild().getLeftChild().setLeftChild(new Node(32));
   root.getLeftChild().getLeftChild().getRightChild()
     .setLeftChild(new Node(87));
   root.getRightChild().getLeftChild().getRightChild()
     .setLeftChild(new Node(29));
   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===============
Level order traversal in zigzag order: 12 18 23 11 43 12 27 98 32 78 56 87 29
==================================

Find sum of all elements of binary tree in Java - Iterative and recursive

Topics covered

1. Sum of nodes of binary tree -Iterative
2. Sum of nodes of binary tree -Recursive
3. Complete sample program

Problem Statement :- Find sum of all nodes of binary tree.

Sum of nodes of binary tree :-  351

Sum of nodes of binary tree - Iterative
Algorithm : Traverse binary tree in level order traversal and sum all nodes of tree.
Time and space complexity:- TC = O(n) and SC = O(n), n is number of nodes of binary tree.
Sample code for finding diameter of binary tree - time complexity O(n^2),

public int iterativeleveSumOfBinaryTreeNodes(Node root) {
 /* java.util.ArrayDeque */
 Queue<Node> queue = new ArrayDeque<>();
 int sum = 0;
 if (root != null) {
  queue.add(root);
  while (!queue.isEmpty()) {
   /* Dequeue form queue and update sum */
   root = queue.remove();
   sum += root.data;
   Node lc = root.leftChild;
   Node rc = root.rightChild;
   if (lc != null) {
    queue.add(lc);
   }
   if (rc != null) {
    queue.add(rc);
   }
  }
 }
 return sum;
}

Sum of nodes of binary tree - Recursive
Algorithm :- Do recursive preorder traversal and add all nodes in static variable.
1. Make recursive call to find height and diameter of left and right subtree
Sample program for find diameter of binary tree - time complexity O(n)

/* preOrder traversal - sum of all nodes */ public void sumOfAllNodesRecursive(Node root) { if (root == null) return; sumRec += root.data; /* Append node data in string buffer */ sumOfAllNodesRecursive(root.getLeftChild()); sumOfAllNodesRecursive(root.getRightChild()); }

Complete sample program- find diameter of binary tree

package com.devinline.trees;

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

public class SumOfAllNodesOfBinaryTree {
 static int sumRec = 0;

 public int iterativeleveSumOfBinaryTreeNodes(Node root) {
  /* java.util.ArrayDeque */
  Queue<Node> queue = new ArrayDeque<>();
  int sum = 0;
  if (root != null) {
   queue.add(root);
   while (!queue.isEmpty()) {
    /* Dequeue form queue and update sum */
    root = queue.remove();
    sum += root.data;
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }
  }
  return sum;
 }

 /* preOrder traversal - sum of all nodes */
 public void sumOfAllNodesRecursive(Node root) {
  if (root == null)
   return;
  sumRec += root.data;
  /* Append node data in string buffer */
  sumOfAllNodesRecursive(root.getLeftChild());
  sumOfAllNodesRecursive(root.getRightChild());
 }

 public static void main(String[] args) {
  SumOfAllNodesOfBinaryTree slo = new SumOfAllNodesOfBinaryTree();
  Node root = slo.new BinaryTree().createTree();
  System.out
    .print("Sum of all nodes of binary" + " tree is(Iterative): ");
  System.out.println(slo.iterativeleveSumOfBinaryTreeNodes(root));
  slo.sumOfAllNodesRecursive(root);
  System.out.print("Sum of all nodes of binary " + "tree is(Recursive): "
    + sumRec);
 }

 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 of all nodes of binary tree is(Iterative): 351
Sum of all nodes of binary tree is(Recursive): 351
==================================

Related question:-
1. Display sum of nodes of at all level- level by level sum calculation.

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
===========================