Check whether a given binary tree is perfect or not in Java

In this tutorial, we will learn to verify if a binary tree is a perfect binary tree or not in Java. There are many ways of solving this problem; here, I have discussed the iterative approach.

A Perfect Binary Tree has all the internal nodes having two children and the leaves at the same level. For example,

       1              1
      / \            / \
     2   3          2    3
    / \  / \       / \  /
   4   5 6  7     4   5 6

The first one is a Perfect Binary Tree whereas the second one is not.

The Logic

We will use a queue and a flag, initialized to zero. We will turn the value of the flag to one only when a leaf node is discovered. Then we will follow these steps:

1. If the present node has two children, we will look at the flag. We will add the nodes to the queue to check them further, provided that the flag value is zero. If the flag is one, return false.
2. If the current node is childless, change the flag to 1 as it is a leaf node.
3. It is not a perfect binary tree, if the current node has only one child. Thus, return False.

Finally, we return a true value, meaning that the binary tree is perfect. Since we look at each iteration, this approach is known as the Iterative Approach.

The Method

Firstly, create a Node class and a newNode method.

static class Node{ 
    int data; 
    Node l, r; 
}; 

static Node newNode(int data){ 
    Node node = new Node(); 
    node.data = data; 
    node.l = node.r = null; 
    return (node); 
}

Next, create a Queue to store the nodes. Initialize the flag value to zero. Check the individual nodes to see whether they have children nodes. If so, check for the value of the flag variable. If 1, return “False”. Otherwise, add the nodes to the queue. If they have single child nodes, stop and return false. If the current node has a single child, set the flag value to 1. In the end, return true.

Queue<Node> q = new LinkedList<Node>(); 

       q.add(root); 

       int flag = 0; 

       while (q.size() > 0){ 
           Node temp = q.peek(); 
           q.remove(); 

           if (temp.l != null && temp.r != null){ 
          
               if (flag == 1) 
                   return false; 

           
               else{ 
                   q.add(temp.l); 
                   q.add(temp.r); 
               } 
           } 

           else if (temp.l == null && temp.r == null){ 
               flag = 1; 
           } 

           else if (temp.l == null || temp.r == null) 
               return false; 
           } 

       return true;

Finally, write the driver code to check the status of the given Binary Tree.

Java Code: A given binary tree is perfect or not

I have provided the entire code. Check it out.

import java.util.*; 

class perfect_tree{ 
    
    static class Node{ 
        int data; 
        Node l, r; 
    }; 

    static Node newNode(int data){ 
        Node node = new Node(); 
        node.data = data; 
        node.l = node.r = null; 
        return (node); 
    } 

    static boolean status_binary_tree(Node root){ 
        Queue<Node> q = new LinkedList<Node>(); 

        q.add(root); 

        int flag = 0; 

        while (q.size() > 0){ 
            Node temp = q.peek(); 
            q.remove(); 

            if (temp.l != null && temp.r != null){ 
           
                if (flag == 1) 
                    return false; 

            
                else{ 
                    q.add(temp.l); 
                    q.add(temp.r); 
                } 
            } 

            else if (temp.l == null && temp.r == null){ 
                flag = 1; 
            } 

            else if (temp.l == null || temp.r == null) 
                return false; 
            } 

        return true; 
    } 

    public static void main(String args[]){ 
        Node root1 = newNode(7); 
        root1.l = newNode(5); 
        root1.r = newNode(6); 
        root1.l.l = newNode(8); 
        root1.l.r = newNode(1); 
        root1.r.l = newNode(3); 
        root1.r.r = newNode(9); 
        root1.r.r.r = newNode(13); 
        root1.r.r.l = newNode(10); 

        Node root2 = newNode(7); 
        root2.l = newNode(5); 
        root2.r = newNode(6); 
        root2.l.l = newNode(8); 
        root2.l.r = newNode(1); 
        root2.r.l = newNode(3); 
        root2.r.r = newNode(9); 
        
        if (status_binary_tree(root1)) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
            
        if (status_binary_tree(root2)) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}

The output is as follows:

No
Yes

I hope this post has been helpful.