How to Count leaf nodes in a binary tree using Recursion in Java

In this post, we will write a Java program to count the leaf nodes in a binary tree. We will use recursion to solve this problem. In a binary tree, each node can have at most two child nodes. A node which has at least one child node is an internal node of the tree. A node which has no left and right subtrees is called a leaf node. So, a leaf node has no child nodes.

Algorithm – Count leaf nodes in a binary tree using Recursion

We will write a recursive program named countLeaves to solve this problem. It takes only one argument which is the root of the binary tree. This function returns an integer value.

1. If the node is null then return 0.
2. If both the left child and right child of the node is null then return 1. As this node is a leaf node of the tree.
3. Call the countLeaves function for the left child of the node.
4. Call the countLeaves function for the right child of the node.
5. Return the sum of leaf nodes from the left and right subtrees.

Program to count leaf nodes of a binary tree in Java

public class CountLeafNodes {
    public static void main(String[] args) {
        /* Tree:
                      50
                     /  \
                    10   20
                  /  \   /  \
                30   60  70  80
                 \       /
                 40     90
         */
        TreeNode root = new TreeNode(50);
        root.left_side_Child = new TreeNode(10);
        root.right_side_Child = new TreeNode(20);
        root.left_side_Child.left_side_Child= new TreeNode(30);
        root.left_side_Child.left_side_Child.right_side_Child = new TreeNode(40);
        root.left_side_Child.right_side_Child = new TreeNode(60);
        root.right_side_Child.left_side_Child = new TreeNode(70);
        root.right_side_Child.right_side_Child = new TreeNode(80);
        root.right_side_Child.left_side_Child.left_side_Child = new TreeNode(90);
        System.out.println("No of leaf nodes = " + countLeaves(root));

         /* Tree:
                      50
                     /  \
                    10   20
                  /  \   /  \
                30   60  70  80
               / \       / \
              100  40  90 110
         */
        TreeNode root1 = new TreeNode(50);
        root1.left_side_Child = new TreeNode(10);
        root1.right_side_Child = new TreeNode(20);
        root1.left_side_Child.left_side_Child = new TreeNode(30);
        root1.left_side_Child.left_side_Child.left_side_Child = new TreeNode(100);
        root1.left_side_Child.left_side_Child.right_side_Child = new TreeNode(40);
        root1.left_side_Child.right_side_Child = new TreeNode(60);
        root1.right_side_Child.left_side_Child = new TreeNode(70);
        root1.right_side_Child.right_side_Child = new TreeNode(80);
        root1.right_side_Child.left_side_Child.l eft_side_Child= new TreeNode(90);
        root1.right_side_Child.left_side_Child.right_side_Child = new TreeNode(110);
        System.out.println("No of leaf nodes = " + countLeaves(root1));

    }

    static class TreeNode {
        int val;
        TreeNode left_side_Child;
        TreeNode right_side_Child;

        TreeNode(int x) {
            val = x;
            left_side_Child = null;
            right_side_Child = null;
        }
    }

    public static int countLeaves(TreeNode node) {

        if (node == null) {
            return 0;
        }
        if (node.right_side_Child == null && node.left_side_Child == null) {
            return 1;
        }

        int count = 0;
        count += countLeaves(node.left_side_Child);
        count += countLeaves(node.right_side_Child);
        return count;
    }
}

Output:

No of leaf nodes = 4
No of leaf nodes = 6

You can also read:

• Check whether a given tree is a Binary Search Tree in Java
• Preorder, Inorder and Postorder traversals without Recursion in Java