4
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Konrad Rudolph Aug 13 '12 at 10:57
  • \$\begingroup\$ @Konrad, yes level means depth. Thanku \$\endgroup\$ – Manish Aug 13 '12 at 17:05
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Leonid Aug 13 '12 at 23:52
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.