Find sum of nodes in binary tree ( java/ non-recursive/ example)

• Given a binary tree, calculate sum of all nodes of a binary tree.
• Traverse the binary tree using level order traversal or breadth first search (bfs) algorithm.
• Accumulate sum at each level of a binary tree & we will get sum of all nodes.

Example: find sum of all nodes in a binary tree using java

The Level order traversal of binary tree shown in Fig 1 is as follows:

• Visit the Level 0 and find out sum at nodes at level o,
  • Total Sum = 55 & Go to next level
• Visit the Level 1 and Sum at Level 1 = 90 (50 + 40).
  • Total Sum = 55 + 90 =   145 & Go to next level
• Visit the Level 2 & Sum at Level 2 = 240 (25+80+45+90)
• Total Sum = 145 + 240 = 385. (Refer Fig 2)

Time complexity of algorithm is O(n).

Program: calculate sum of nodes in java using non recursive algorithm

1.) SumOfNodes Class:

• SumOfNodes class is responsible for calculating sum of all nodes in a binary tree using BFS algorithm.

package org.learn.Question;

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

public class SumOfNodes {

 public static int sumOfNodes(Node root) {
  if (root == null) {
   System.out.println("Tree is empty");
   return -1;
  }
  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);
  int totalSum = 0;
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   totalSum += node.data;
   if (node.left != null) {
    queue.offer(node.left);
   }
   if (node.right != null) {
    queue.offer(node.right);
   }
  }
  return totalSum;
 }
}

2.) Node Class:

• Node class is representing the nodes of a binary tree.

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }

 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

• We are creating the binary tree in main method.
• We are calling method of SumOfNodes class, to calculate the sum of all nodes using BFS algorithm.

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.SumOfNodes;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(55);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(40);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(80);
  Node F = Node.createNode(45);
  Node G = Node.createNode(90);

  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;
  int totalSum = SumOfNodes.sumOfNodes(A);
  System.out.println("Sum of nodes in a binary tree : " + totalSum);
 }
}

Output: find sum of nodes in java using recursive algorithm

Sum of nodes in a binary tree : 385

     Download code – sum nodes binary tree (BFS)