Find level in binary tree having maximum sum (java/ non-recursive/ example)

• Given a binary tree, find out the level, which is having maximum sum using non recursive algorithm.
  • Traverse the binary tree using level order traversal or breadth first search (BFS) algorithm.
• Root node of binary tree is at level 0.
  • We can find out the level of rest of nodes wrt. root node.
• We have discussed the similar problem, find out the height of binary tree using level order traversal.

Example: Find level having maximum sum in a binary tree (java)

Find out the level, which having maximum sum, for a given binary tree shown in Fig 2. Let us calculate the sum at each level.

In a given binary tree, Level 2 has maximum sum of 240.

Algorithm: find level having max sum in a binary tree (iterative method)

• Root is at level 0, push root node to queue.
• Create variable to store maxSum & level.
• Push null as level delimiter, to the queue.
• Iterate through the Queue
  • Calculate the local sum
  • Pop node from queue
  • If popped up node is null,
    •  We are at next level.
      • Update maxSum if it is less than local sum.
        • Save the level of local sum.
• Add next level children (left or/and right nodes)
• Once we exit the loop, we will get the maximum sum and level.

Time complexity of algorithm is O(n).

Program: find out level having max sum in java (breadth first search algo.)

1.) MaxSumLevel Class:

• MaxSumLevel class is responsible for finding the level, which is having maximum sum.
• Traverse the binary tree using level order traversal or breadth first search algorithm.

package org.learn.Question;

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

public class MaxSumLevel {
	public static void maxSumLevel(Node root) {
		if (root == null) {
			System.out.println("Tree is empty");
			return;
		}
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		// level delimiter
		queue.offer(null);

		int maxSum = 0;
		int level = 0;
		// default root level
		int localLevel = 0;
		int localSum = 0;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			// Level change
			if (null == node) {
				if (!queue.isEmpty()) {
					// level delimiter
					queue.offer(null);
				}

				if (localSum > maxSum) {
					maxSum = localSum;
					level = localLevel;
				}
				// Reset the level sum for next level calculation
				localSum = 0;
				localLevel++;
			} else {
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
				localSum += node.data;
			}
		}
		System.out.println("Max Sum = " + maxSum + " is at Level = " + level);
	}
}

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 calling the method of MaxSumLevel class, to find the level, which is having maximum sum.

package org.learn.Client;

import org.learn.Question.MaxSumLevel;
import org.learn.Question.Node;

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);
		// Level 3
		Node H = Node.createNode(10);
		Node I = Node.createNode(35);
		Node J = Node.createNode(65);
		Node K = Node.createNode(75);

		// 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;
		// connect level 2 and level 3
		F.left = H;
		F.right = I;
		G.left = J;
		G.right = K;
		MaxSumLevel.maxSumLevel(A);
	}
}

Output: level in a binary having maximum sum using java

Max Sum = 240 is at Level = 2

Download code – find level in binary tree maximum sum in java