Java program to count number of leaf nodes in a tree
Here's a Java program to count the number of leaf nodes in a tree:
class Node { int value; Node left; Node right; public Node(int value) { this.value = value; left = null; right = null; } } class BinaryTree { Node root; public BinaryTree() { root = null; } // Recursive function to count the number of leaf nodes public int countLeafNodes(Node node) { if (node == null) { return 0; } else if (node.left == null && node.right == null) { return 1; } else { return countLeafNodes(node.left) + countLeafNodes(node.right); } } } public class CountLeafNodes { public static void main(String[] args) { // Create a binary tree 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); // Count the number of leaf nodes int leafCount = tree.countLeafNodes(tree.root); System.out.println("Number of leaf nodes in the tree: " + leafCount); } }
This program defines a Node
class to represent nodes in the tree, and a BinaryTree
class to represent the tree itself. The BinaryTree
class has a method called countLeafNodes()
that recursively counts the number of leaf nodes in the tree. The countLeafNodes()
method takes a Node
object as an argument, and returns the number of leaf nodes in the subtree rooted at that node.
The countLeafNodes()
method first checks if the current node is null. If it is, it returns 0. If the current node has no children, it is a leaf node, and the method returns 1. Otherwise, the method recursively calls itself with the left and right children of the current node, and returns the sum of the leaf nodes in those subtrees.
The main()
method creates a binary tree and calls the countLeafNodes()
method on the root node to count the number of leaf nodes in the tree. The result is printed to the console.