Count Leaf Nodes in a Tree with Java Recursion

Unraveling the Power of Recursion: A Java Program to Count Leaf Nodes

When it comes to navigating complex data structures, recursion is a powerful tool in a programmer’s arsenal. In this article, we’ll explore a Java program that harnesses recursion to count the number of leaf nodes in a tree.

The Tree Data Structure: A Brief Overview

Before diving into the program, let’s take a step back and examine the tree data structure. A tree is a hierarchical collection of nodes, where each node has a value and zero or more child nodes. This structure is particularly useful for representing relationships between data entities.

The Java Program: Counting Leaf Nodes with Recursion

Now, let’s get to the meat of the matter – the Java program that counts leaf nodes using recursion. Here’s the code:

“`java
// Java program to count the number of leaf nodes in a tree
class Node {
int data;
Node left, right;

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

}

class BinaryTree {
Node root;

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);
}

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("Leaf count = " + tree.countLeaves(tree.root));
}

}
“`

How Recursion Works Its Magic

So, how does this program use recursion to count leaf nodes? The key lies in the countLeaves method. This method takes a node as an argument and returns the number of leaf nodes beneath it. If the node is null, the method returns 0. If the node is a leaf node (i.e., it has no left or right child), the method returns 1. Otherwise, the method recursively calls itself on the left and right child nodes, adding up the results.

The Output: A Leaf Node Count

When we run this program, it outputs the number of leaf nodes in the tree. In this case, the output is:


Leaf count = 3


This result makes sense, since the tree has three leaf nodes: 4, 5, and 3.

Recursion in Action

By using recursion, this program is able to elegantly navigate the tree data structure and count leaf nodes with ease. Recursion allows us to break down complex problems into smaller, more manageable pieces, making it an essential tool in any programmer’s toolkit.