Return to Revisions

Okay lets start with the name of your function: leavesIn1Level(...). It does explain what this method does, but apparently it is not very clear - even to yourself - therefore you felt the need to add a comment. How a bout the name areAllLeavesInSameLevel(..). This explais what it does and makes your comment useless.

Next point (a compliment): You used a Queue, which is the data-structure that fits your needs perfectly. Good job.

One thing I noticed: The line node.left == null && node.right == null is used twice in your short piece of code and therefore - code duplication. How do we get rid of it? Well... What does that line of code do? It checks whether a Node is a Leaf. So why don't we just name it that way?

private static boolean isLeaf(Node node)
{
    return node.left == null && node.right == null;
}

Boom. Code duplication gone. And the code explains exactly what it does.

Now what I realized, is that you have a very deep level of abstraction in this function, where you mix what is done with how its done. Lets try to get rid of this:

if(current.left != null){
    q.add(current.left);
}
if(current.right != null){
    q.add(current.right);
}    

This piece of code explains how something is done. But what is done? Children of a node are added to a queue. Why don't we just name it that?

private static void addChildrenToQueue(Node node, Queue<Node> queue)
{
    if(node.left != null){
        queue.add(node.left);
    }
    if(node.right != null){
        queue.add(node.right);
    }    
}

Lets take a look at what we have now:

public static boolean areAllLeavesInSameLevel(Node root){

    if(root == null){
        return false;
    }           
    if(isLeaf(root)){
        return true;
    }
    Queue<Node> q = new LinkedList<Node>(); 
    q.add(root);

    int levelNumber = 0;
    int height = height(root);

    while(true){

        int nodeCount = q.size();           
        if(nodeCount == 0){
            break;
        }   
        while(nodeCount > 0){

            Node current = q.remove();
            nodeCount--;

            if(isLeaf(current)){
                if(height != levelNumber){
                    return false;
                }else{
                    return true;
                }
            }
            addChildrenToQueue(current,q); 
        }           
        levelNumber++;
    }
    return false;
}

Now I'm not particularly happy with the name q. What is inside that queue? It's nodes that need to be checked - in other words: remainingNodes. Lets just call it that.

Take a look at this:

while(true){
    int nodeCount = remainingNodes.size();           
    if(nodeCount == 0){
        break;
    }
    ...
}
return false;

What does it do? If the queue is empty it jumps out of the loop and then returns false. How about we move it around a bit to get rid of that while(true):

while(!remainingNodes.isEmpty()){
    int nodeCount = remainingNodes.size(); 
    ...
}
return false;

Aaaand the while(true) is gone and replaced with a much better phrased condition. While the Collection of remaining nodes is not empty do something. At this point we can argue that the queue could have the even better name queueOfRemainingNodes. Some would say it's too long. I like it, but that's up to you to decide.

Let's take a look at the second while:

int nodeCount = queueOfRemainingNodes.size();   
while(nodeCount > 0){
    nodeCount--;
    ...
}

To me this looks like the classic case for a for-loop instead:

for(int nodeCount = queueOfRemainingNodes.size(); nodeCount > 0; nodeCount--)
{
    ...
}

Okay. Now what does this inner for-loop actually do? It checks whether any node, that is currently in the queue is a leaf and if it is not, it adds its children to the queue. If however one is a leaf, it does the following check:

if(height != levelNumber){

What? Is height euql to levelNumber? What is levelNumber? And which height? By looking up we find out that height is the height of the tree and levelNumber is the number of the level we are currently looking at. Let's give these two some more expressive names:

int currentLevelNumber = 0;
int treeHeight = height(root);

So where are we now? Let's take a look at the full code:

public static boolean areAllLeavesInSameLevel(Node root){

    if(root == null){
        return false;
    }           
    if(isLeaf(root)){
        return true;
    }
    Queue<Node> queueOfRemainingNodes = new LinkedList<Node>(); 
    queueOfRemainingNodes.add(root);

    int currentLevelNumber = 0;
    int treeHeight = height(root);

    while(!queueOfRemainingNodes.isEmpty()){

        for(int nodesOnCurrentLevel = queueOfRemainingNodes.size(); nodesOnCurrentLevel > 0; nodesOnCurrentLevel--){

            Node current = q.remove();

            if(isLeaf(current)){
                if(treeHeight != currentLevelNumber){
                    return false;
                }else{
                    return true;
                }
            }
            addChildrenToQueue(current,queueOfRemainingNodes); 
        }           
        currentLevelNumber++;
    }
    return false;
}   

Wow. Just realized how long this post got. Sorry, I could go on for hours and remove this second (and third) level of intendation and find more expressive names for everything, but I think this gives you an impression on what you can do.