- 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.
| Level | Nodes | Sum |
|---|---|---|
| 0 | A | 55 |
| 1 | B,C | 90 |
| 2 | D,E,F,G | 240 |
| 3 | H,I,J,K | 185 |
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.
- Update maxSum if it is less than local sum.
- We are at next level.
- 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 |