Java Program to Count number of leaf nodes in a tree

Introduction

In computer science, leaf nodes in a tree data structure represent the nodes without any children. These are the terminal nodes of the tree. Counting the number of leaf nodes is a frequently encountered task, which is useful in understanding the structure or the depth of a tree, among other things.

In this article, you will learn how to count the number of leaf nodes in a binary tree using Java. You'll explore a step-by-step approach using recursive methods, which are ideal for traversing tree structures. Also, you will see how to create a simple binary tree and apply the leaf counting method using concrete examples.

Understanding the Basic Tree Structure

Define the Node Class

1. Define a class Node which will be the building block of the tree. Each node object will represent a single node in the tree.

   java Copy

   class Node {
       int data;
       Node left, right;
   
       Node(int item) {
           data = item;
           left = right = null;
       }
   }
   

   The Node class contains three attributes:

   • data holds the integer value at this node.
   • left and right are references to the left and right children of the node, respectively.

Construct the Tree Structure

1. Create a class BinaryTree that represents the whole tree.

2. Provide a constructor to initialize the tree and a method to count leaf nodes.

   java Copy

   class BinaryTree {
       Node root;
   
       BinaryTree() {
           root = null; // Tree is initially empty
       }
   
       int countLeaves(Node node) {
           if (node == null)      
               return 0;
           if (node.left == null && node.right == null)     
               return 1;
           else     
               return countLeaves(node.left) + countLeaves(node.right);
       }
   
       int getLeafCount() {
           return countLeaves(root);
       }
   }
   

   In the BinaryTree class:

   • The root attribute will point to the root node of the binary tree.
   • The countLeaves method is a recursive function that:
     • Returns 0 if the node is null.
     • Returns 1 if the node is a leaf (both left and right children are null).
     • Recursively counts the leaf nodes in both left and right subtrees otherwise.

Implementing and Testing the Leaf Counter

Setting Up the Tree

1. Instantiate the BinaryTree class and manually create nodes to form a tree.

   java Copy

   public class Main {
       public static void main(String[] args) {
           BinaryTree tree = new BinaryTree();
           tree.root = new Node(1);
           tree.root.left = new Node(2);
           tree.root.right = new Node(3);
           tree.root.left.left = new Node(4);
           tree.root.left.right = new Node(5);
   
           System.out.println("The number of leaf nodes is " + tree.getLeafCount());
       }
   }
   

   This example hard-codes the tree structure:

       1
      / \
     2   3
    / \
   4   5

   Here, the nodes containing the values 3, 4, and 5 are leaf nodes.

Execution and Output

1. The output of running the Main class would be:

   The number of leaf nodes is 3

   This correctly reflects the count of leaf nodes, as visualized in the tree diagram above.

Conclusion

Counting leaf nodes in a binary tree is a fundamental problem that can be efficiently solved using recursion. The Java program demonstrated provides a clear method to achieve this through a combination of class structures and recursive functions. Adapting this solution to different types of tree structures or to include additional features, such as counting only left or right leaf nodes, can further your understanding and manipulation of tree-based data structures. By mastering these techniques, you enhance your ability to implement efficient and organized code for various computational problems involving trees.