Write a Java Program to Count number of leaf nodes in a tree

In computer science, a tree is a non-linear data structure that consists of nodes connected by edges.

Each node can have zero or more children, and a node with no children is called a leaf node.

In this tutorial, we’ll explore how to count the number of leaf nodes in a tree using Java programming language.

To solve this problem, we can use a recursive approach where we traverse the tree and count the number of leaf nodes.

Here’s the Java code:

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    public int countLeafNodes() {
        return countLeafNodes(root);
    }

    private int countLeafNodes(Node node) {
        if (node == null) {
            return 0;
        }

        if (node.left == null && node.right == null) {
            return 1;
        }

        return countLeafNodes(node.left) + countLeafNodes(node.right);
    }
}

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

        int count = tree.countLeafNodes();
        System.out.println("Number of leaf nodes in the tree: " + count);
    }
}

In the above code, we first define a Node class that represents a node in the tree.

The Node class has a data field that stores the value of the node and left and right fields that represent the left and right children of the node.

Next, we define a BinaryTree class that represents the tree itself.

The BinaryTree class has a root field that stores the root node of the tree.

We also define a countLeafNodes method that returns the number of leaf nodes in the tree.

This method calls a private helper method countLeafNodes that actually does the counting.

The countLeafNodes method takes a Node parameter and recursively counts the number of leaf nodes in the subtree rooted at the given node.

If the given node is null, it returns 0. If the given node has no children, it returns 1.

Otherwise, it recursively counts the number of leaf nodes in the left and right subtrees and returns their sum.

Finally, in the main method, we create a tree and count the number of leaf nodes using the countLeafNodes method.

We print the result to the console.

That’s it! We have successfully written a Java program to count the number of leaf nodes in a tree using a recursive approach.

This solution is simple, elegant, and efficient, with a time complexity of O(n), where n is the number of nodes in the tree.

Tags

Related Posts