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.

Sum nodes binary tree — Fig 1: Calculate sum of 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)

Sum each level tree bfs — Fig 2: Sum at each level

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

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

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

1.) SumOfNodes Class:

2.) Node Class:

3.) App Class:

Output: find sum of nodes in java using recursive algorithm

You may also like: