How to find the maximum sum level in binary tree in Java? Example Tutorial

Hello guys, if you are preparing for a coding interview and wondering how to find the maximum sum level in a given binary tree in Java then you have come to the right place. I have been sharing binary tree coding problems for the last few months and in the past, we have seen questions like finding kth smallest element and finding the lowest common ancestor of a binary tree in Java in this article, you will learn how to find the maximum sum level in a given binary tree of integers or numbers. But, before finding the maximum sum level of a binary tree in java, we need to have a good understanding of a binary search tree. Both theoretical knowledge and how to implement binary search tree in Java is important to solve tree-based coding problems. 

A Binary tree is a data structure in which each node can have at most two children. That is, each node in the binary tree will have data, left child and right child. The first node of the tree is called the Root.

Below is the image of the Binary search tree, all the green circles are called nodes and they have at most two other nodes called children.

Fig 1.0 Binary search tree.

In the diagram above, The root node is node 8 as you can see, And it has two Children node 3 and node 10, left and right respectively. Node 3 also has two children nodes 1 and 6. Node 6 has two children, node 4 and node 7 respectively, And to the right side of node 8 which is node 10, has just only one child, node 14, node 14 to has only one child. Nodes 4, 7, and 13 are called leaves because they do not have children.

Here are few important things to note when determining is if a tree is a binary tree or not:

• All data in the nodes of the left sub-tree are lesser than the right.
• In the Children nodes, All data on the left are lesser than the right.
• All data in the nodes of the left sub-tree is lesser than the root
• All data in the nodes of the right sub-tree is greater than the root.

So, with all these bullet points you can determine if a tree is a binary tree or not. We shall we do a task to find out for better understanding.

Given a Binary tree, we want to find the maximum sum level in the tree. By now, you should understand what a binary tree is. So, what we are doing in the task is to find the maximum sum level, if you check closely you would see that the root which is node 8 is the first level, the second level is node 3, and node 10, the third level is node 1, node 6 and node 14, while the fifth level node 4, node 7 and node 13.

Java Program to find the Maximum Sum Level in Given Binary Search Tree - Example

Below is the implementation for better understanding:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

public class MaximumSumLevel { Node root; int globalMax; public MaximumSumLevel() { //creating 1st level, the root. root = new Node(3); // Creating 2nd level: Node one = new Node(2); Node two = new Node(20); root.left = one; root.right = two; // Creating 3rd level: Node three = new Node(7); Node four = new Node(5); Node five = new Node(-8); one.left = three; two.left = four; two.right = five; } public int findMaxLevel(Node root) { if (root == null) return 0; // recursive calls: int left = findMaxLevel(root.left); int right = findMaxLevel(root.right); // Max of first three cases: int maxOfThree = Math.max(Math.max(left, right) + root.val, root.val); // Max of all four cases: int maxOfFour = Math.max(returnMax, root.val + left + right); // Update globalMax: if (maxOfFour > globalMax) globalMax = maxOfFour; // Return value to parent caller: return maxOfThree; } public static void main(String[] args) { MaximumSumLevel maxSum = new MaximumSumLevel(); m.findMaxLevel(maxSum.root); System.out.println("Maximum possible sum in a path: " + maxSum.globalMax); } }

From Line 1 to 20, there are two classes embedded there, the class “Node” in the class “MaximumSumLevel” with the constructor starting from line 4 which initializes the root to 3 in line 8 which was the first level.

Line 8 and 9 instantiates Node one and Node two to 2 and 20 and assign it to root.left and root.right respectively as you can see in lines 10 and 11 which is the second level. The same thing applied in creating the third level from lines 13 to 18.

In line 20, the method “findMaxLevel” was created which takes in a parameter, root of type Node. Line 21 is validating if the root is null it should return 0. but, if not it proceeds to do what was stated in the following lines, (This is the same thing as else too).

Line 24 and line 25 are variables left and right that hold the method itself as it’s been called(Recursion) and assigns them respectively. Note that, as the method is been recalled it’s taking different parameters based on what is storing them, either left or right.

In Line 27, Math.max() method was called, an inbuilt method in Java that takes two numbers and returns the maximum number between the two. But because the maximum number we are looking for is not between two numbers. It is more than two.

So, we have to call it two times rightly placed inside each other. Then, the same thing with line 29 with the appropriate parameters inside of it.

After that, the variable “globalMax” that was declared first at the Node’s class instance variable was updated, with the conditions that: if maxOfFour is greater than what we have in globalMax at initialization it should re-assign globalMax to maxOfFour. And line 34 returns value to the parent caller.

Line 36 is the main Method. Line 37 creates an instance of the class MaximumSumLevel which was “maxSum”. The method was called in line 38 and it was printed in line 39.

Output:
The maximum possible sum in a path: 21

That's all about how to find the maximum sum level in a given binary tree in Java. This is an important question and if you are serious about doing well on the technical or coding interviews, you should practice binary tree-based coding questions like this. If you need more questions you can also ways check out the following resources


Other data structure and algorithms tutorials for Java Programmers

• Top 50 Java Programs from Coding Interviews (see here)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• How to check if a String is a Palindrome in Java? [solution]
• How to find the missing number in a sorted array in Java? [answer]
• 10 Algorithms Books Every Programmer Should Read (books)
• 10 Algorithm books Every Programmer Should Read (list)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• How to remove an element from the array without using a third-party library (check here)
• How to implement the Quicksort algorithm in Java? (solution)
• 5 Books to learn data structure and algorithms in Java? (books)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)
• How to print the Fibonacci series in Java without using Recursion? [solution]
• How to check if an integer is a power of two without using division or modulo operator?[hint]
• How to find all permutations of String in Java? [solution]
• Top 20 String coding interview questions (see here)
• How to find the largest and smallest number in an array in Java (read here)
• How to find two maximum numbers on an integer array in Java (check here)

If you have any suggestions to make this algorithm better, feel free to suggest. The interviewer loves people who come up with their own algorithms or give some touch to popular algorithms.


P. S. - If you don't mind learning from free resources then you can also take a look at my list of free data structure and algorithm courses for Java developers. It contains some free online courses from Udemy, Coursera, edX, and other resources for Java developers.