Check if all leaves are at same level in a binary tree

Question

I have written this code for checking whether all leaves are in the same level or not, in a binary tree. Any suggestion or improvement is appreciated.

import java.util.LinkedList;
import java.util.Queue;

public class Methods {      

    //* ---- Method for check whether all leaves are in the same level or not --- *         
    public static boolean leavesIn1Level(Node root){

        if(root == null){
            return false;
        }           
        if(root.left == null && root.right == null){
            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(current.left == null && current.right == null){
                    if(height != levelNumber){
                        return false;
                    }else{
                        return true;
                    }
                }
                if(current.left != null){
                    q.add(current.left);
                }
                if(current.right != null){
                    q.add(current.right);
                }           
            }           
            levelNumber++;
        }
        return false;
    }

    //* ---- Method for finding height of a binary tree ---- *  
    public static int height(Node root){

        if(root == null){
            return -1;

        }else{

            return Math.max(height(root.left), height(root.right))+1;
        }
    }


    public static void main(String[] args) {

        Node root1 = new Node(8);                      //              8
        root1.left = new Node(9);                      //             / \
        root1.right = new Node(5);                     //            9   5                           
        root1.left.left = new Node(4);                 //           /   /
        root1.right.left = new Node(1);                //          4   1
        root1.right.left.left = new Node(3);           //             /
        root1.right.left.left.left = new Node(2);      //            3                  
                                                       //           /
                                                       //          2

        Node root2 = new Node(1);                      //              1
        root2.left = new Node(2);                      //             /  \
        root2.right = new Node(3);                     //           2     3
        root2.left.left = new Node(4);                 //          / \   /
        root2.left.right = new Node(5);                //        4    5 6 
        root2.right.left = new Node(6);


        System.out.println(leavesIn1Level(root1));
        System.out.println(leavesIn1Level(root2));
   }
}

Node class:

public class Node {
    int data;
    Node left;
    Node right;     
    public Node(int d){
        data = d;
        left = null;
        right = null;
    }
}

This code is different from: Check if all leaves are at same level

Answer 1

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 equal 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.

Answer 2

• Algorithm

  A computation of height is redundant. The code processes a tree level by level, so the natural continuation condition is that the level contains only non-leaves:

  while (!q.isEmpty()) {
          ...
          if (isLeaf(current)) {
              leafs++;
          } else {
              add_children();
              internals++;
          }
          if (leafs == 0) {
              continue;
          }
          return internals == 0;
      }
  

• Unreachable code

  Getting out of the while (true) loop via nodeCount == 0 condition implies that we traversed the whole tree and encountered no leaves. It is logically impossible and if the program follows this path, then there is a bug. Returning false would only mask it. Better raise an exception instead.

• Don't spell out logics

  Instead of

              if(height != levelNumber){
                  return false;
              }else{
                  return true;
              }
  

  use

              return height == levelNumber;
  

Answer 3

Just improving @LorToso answer (with an answer instead of an unreadable comment):

About the algorithmic aspect, I think that currentLevelNumber and int treeHeight = height(root); (which is a bit inefficient because it needs to look at the whole tree) could be replaced with a boolean variable leafAlreadyFound.

Then the full code could be:

public static boolean areAllLeavesInSameLevel(Node root){

    if(root == null){
        return false;
    }           

    boolean leafAlreadyFound = false;
    Queue<Node> queueOfRemainingNodes = new LinkedList<Node>(); 

    queueOfRemainingNodes.add(root);

    while(!leafAlreadyFound && !queueOfRemainingNodes.isEmpty()){

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

            Node current = q.remove();

            if(isLeaf(current)){
                leafAlreadyFound = true;
            } else if(leafAlreadyFound){
                return false;
            } else {
                addChildrenToQueue(current,queueOfRemainingNodes); 
            }
        }           
    }
    return queueOfRemainingNodes.isEmpty();
}   

And as a bonus, the specific condition at the beginning is removed

    if(isLeaf(root)){
        return true;
    }

It addresses all concerned raised by @vnp (and reads as few nodes of the tree as possible)