Check whether a binary tree is a full binary tree or not in Java

In this tutorial, we will learn to check whether a binary tree is full or not in Java. There are many ways to tackle this problem; I am going to use the Recursive Method here.

A Binary Tree is said to be full when all the nodes of the tree have either two or zero child nodes. Thus, we can also say that a Full Binary Tree does not have any single child nodes.

There are a few cases we need to keep in mind to solve this problem.

1. The tree is full if a node has nothing in it i.e. Null.
2. If a node does not have empty subtrees, on either side, the tree is full
3. If a binary tree has left and right subtrees, we will have to recursively check them individually to see whether they are full or not.

In any other case, the binary tree is not full.

Coming to the code, we will make a recursive function. It will check whether the root node has NULL value or whether they have empty left and right subtrees, in which case it will return TRUE. If there are left and right subtrees, it will run a recursion to check them. Otherwise, it will return FALSE.
Finally, we make the driver code and test different cases to see the effectiveness of the code.

static boolean status_binary_tree(Node node){ 
            
    if(node == null) 
        return true; 
               
             
    if(node.l == null && node.r == null ) 
        return true; 
               
             
             
    if((node.l!=null) && (node.r!=null)) 
        return (status_binary_tree(node.l) && status_binary_tree(node.r)); 
               
             
    return false; 
}

The Code and the Output

I have provided the entire code below.

class full_bin_tree_rec{
        
    static class Node{ 
        int value; 
        Node l, r; 
       
        Node(int data){ 
            value = data; 
            l = r = null; 
        } 
    }
        
    static class BinaryTree{ 
        Node root; 
        
        static boolean status_binary_tree(Node node){ 
            
            if(node == null) 
                return true; 
               
             
            if(node.l == null && node.r == null ) 
                return true; 
               
             
             
            if((node.l!=null) && (node.r!=null)) 
                return (status_binary_tree(node.l) && status_binary_tree(node.r)); 
               
             
            return false; 
        }
    }
    
    public static void main(String args[]){ 
        BinaryTree tree1 = new BinaryTree(); 
        tree1.root = new Node(10); 
        tree1.root.l = new Node(20); 
        tree1.root.r = new Node(30); 
        tree1.root.l.r = new Node(40); 
        tree1.root.l.l = new Node(50); 
        
        BinaryTree tree2 = new BinaryTree(); 
        tree2.root = new Node(10); 
        tree2.root.l = new Node(20); 
        tree2.root.r = new Node(30); 
        tree2.root.l.r = new Node(40); 
        tree2.root.l.l = new Node(50); 
        tree2.root.r.l = new Node(60);
        
        if(tree1.status_binary_tree(tree1.root)) 
            System.out.println("The binary tree is a full one."); 
        else
            System.out.println("The tree is not a full one.");
            
        if(tree2.status_binary_tree(tree2.root)) 
            System.out.println("The binary tree is a full one."); 
        else
            System.out.println("The tree is not a full one.");
    }
}

Thus, the output is as follows:

The binary tree is a full one.
The tree is not a full one.

I hope this post has been helpful. Thank you.