Question 60 : How to count leaf nodes of binary tree.

You need to write a java program to count leaf nodes of a binary tree.

The count of Leaf nodes for the binary tree used in Question 15 is 5.

Algorithm-

Steps for counting number of leaf nodes are:

• If node is null then return 0
• If encountered leaf node(i.e. node.left is null and node.right is null) then return 1.
• Recursively calculate number of leaf nodes using

Number of leaf nodes= number of leaf nodes in left subtree + number of leaf nodes 

Code for recursion will be:

// Recursive Solution
    /* To get the count of leaf nodes in a binary tree*/
    public static  int getLeafCountOfBinaryTree(TreeNode node)
    {
        if(node == null)      
            return 0;
        if(node.left ==null && node.right==null)     
            return 1;           
        else
            return getLeafCountOfBinaryTree(node.left)+ getLeafCountOfBinaryTree(node.right);     
    }

Let's create a java program for counting the 

A number of leaf nodes:

public class BinaryTreeLeafCount {
 
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
 
    // Recursive Solution
    /* To get the count of leaf nodes in a binary tree*/
    public static  int getLeafCountOfBinaryTree(TreeNode node)
    {
        if(node == null)      
            return 0;
        if(node.left ==null && node.right==null)     
            return 1;           
        else
            return getLeafCountOfBinaryTree(node.left)+ getLeafCountOfBinaryTree(node.right);     
    }
 
    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Number of leaf nodes in binary tree :"+getLeafCountOfBinaryTree(rootNode));
    }
 
    public static TreeNode createBinaryTree()
    {
 
        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
 
        rootNode.left=node20;
        rootNode.right=node60;
 
        node20.left=node10;
        node20.right=node30;
 
        node60.left=node50;
        node60.right=node70;
 
        return rootNode;
    }
}
 

Run the above program and you will get the following output:

Number of leaf nodes in binary tree :4

Don't miss the next article! 

Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest