# Binary tree max sum level - better design?

I have written some code for finding a level in a binary tree, having a maximum number of elements. I have a few questions:

1. Is it a good design? I have used 2 queues but the total sum of elements both queues store will be less than n. So I think it should be OK.
2. Can there be a better design?

``````    public class MaxSumLevel {
public static int findLevel(BinaryTreeNode root) {
Queue mainQ = new Queue();
Queue tempQ = new Queue();
int maxlevel = 0;
int maxVal = 0;
int tempSum = 0;
int tempLevel = 0;
if (root != null) {
mainQ.enqueue(root);
maxlevel = 1;
tempLevel = 1;
maxVal = root.getData();
}
while ( !mainQ.isEmpty()) {
BinaryTreeNode head = (BinaryTreeNode) mainQ.dequeue();
BinaryTreeNode left = head.getLeft();
BinaryTreeNode right = head.getRight();
if (left != null) {
tempQ.enqueue(left);
tempSum = tempSum + left.getData();
}
if (right != null) {
tempQ.enqueue(right);
tempSum = tempSum + right.getData();
}
if (mainQ.isEmpty()) {
mainQ = tempQ;
tempQ = new Queue();
tempLevel ++;
if (tempSum > maxVal) {
maxVal = tempSum;
maxlevel = tempLevel;
tempSum = 0;
}
}
}
return maxlevel;
}
}
``````
-
This looks pretty complex. What’s the “level” (since you are obviously not using the usual definition by returning an `int`)? Does it correspond to the depth of a node? If so, there’s a much simpler solution. – Konrad Rudolph Aug 13 '12 at 10:57
@Konrad, yes level means depth. Thanku – Manish Aug 13 '12 at 17:05
You definitely over-complicated things. Simpler solutions do exist. leetcode.com/2010/04/maximum-height-of-binary-tree.html stackoverflow.com/questions/9323036/… Note that you could change the data structure such that it keeps the depth of every node as well as the max depth (or better yet, a reference to the deepest node) at all times. This will result in a bit more space, a bit more time, but will make your problem very easy - a simple `O(1)` function call. – Leonid Aug 13 '12 at 23:52

My initial criticism is that your method doesn't have javadoc comments that state clearly and unambiguously what the method is supposed to do.

Why am I saying that?

Well, mainly because your Question has exactly the same problem! You say:

I have written some code for finding a level in a binary tree, having a maximum number of elements.

This is bad description of what you are (apparently) trying to do:

• The word "level" usually refers to the distance of a node from (say) the root of a tree. But you apparently mean the "height" of the entire tree.
• The phrase "having a maximum number of elements" is unclear. What are you talking about? How does this affect the problem? (I don't see a maximum number of elements parameter ... or any reference to this in your code.)

So why does this matter?

Because I (the reader) should not have to read through your code to try to figure out the problem you are trying to solve. Especially if your implementation is non-obvious ... which it is ... and possibly contains mistakes that might lead me to think it is solving a different problem than you are actually trying to solve.

-

First, I notice that you are not using generics; I would prefer `Queue<BinaryTreeNode>` over simply `Queue`.
You could use the standard Java Queue interface. The LinkedList implementation should provide all you need for this snippet.

Second, I'm a little surprised that you use iteration; a recursive solution would be a lot more intuitive, and is almost exactly the same as what you would get if you were to use a `Stack` instead of a `Queue`. And it looks like changing from `Queue` to `Stack` would not change the result of the computation.

It looks like you are both calculating `maxLevel` and `maxVal`, but only returning `maxLevel`. Trying to calculate both smells like premature optimization; I would prefer to write separate methods for these calculations.
Drifting somewhat off-topic, but Java 8 is scheduled to have lambda expressions, so you might then be able to have one tree traversal method and pass it appropriate lambda expressions.

-