Java Program to Count number of leaf nodes in a tree
What are Trees?
In Java, a tree is a data structure that is similar to a linked list, but with a hierarchical structure. Each node in a tree has a value and one or more child nodes, and the topmost node is called the root. Trees are commonly used to implement algorithms such as search, sorting, and traversal.
In this Article, we will write a program to Count number of leaf nodes in a tree.
Tree Class:
There is no specific “Tree” class in the core Java libraries. However, the Java Collections Framework does provide several classes that are based on tree data structures. These include the TreeSet and TreeMap classes.
The TreeSet class is a collection that stores elements in a sorted order. The TreeMap class is a map that stores key-value pairs in a sorted order.
Both TreeSet and TreeMap classes provide useful methods for adding, removing, and searching for elements, as well as for traversing the tree in different ways.
Additionally, there are also several other classes in the Java libraries that can be used to implement trees, such as ArrayDeque, LinkedList, and PriorityQueue. Additionally, there are several third party libraries such as Google’s Guava, Apache’s Commons, and others that provide Tree data structures.
What are Nodes?
In a tree data structure, a node is a basic unit that stores data and has one or more child nodes. Each node has a value, and it can be connected to other nodes through links called edges. The topmost node in the tree is called the root, and it has no parent node. The nodes that have no children are called leaf nodes. The nodes that have one or more children are called internal nodes.
Pre-order Tree Traversal
Java Program to Count number of leaf nodes in a tree:
import java.util.*;
public class Main{
public static void main(String[] args){
// Creating object of BinaryTree class
BinaryTree tree = new BinaryTree();
// Creating Nodes of tree class
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);
// Printing the Tree Structure
System.out.println("The number of leaf nodes is: " + tree.countLeafNodes(tree.root));
}
}
// Node class to create a Node structure
class Node{
// data node
int data;
Node left, right;
// Constructor for node class
Node(int key) {
data = key;
left = right = null;
}
}
// Structure for Tree class
class BinaryTree {
// Root node
Node root;
// Function to Create Tree Structure
int countLeafNodes(Node node) {
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
else
return countLeafNodes(node.left) + countLeafNodes(node.right);
}
}
Output: The number of leaf nodes is: 3
Explanation:
This program uses a recursive approach to count the number of leaf nodes. The method countLeafNodes(Node node) takes a node as an input and checks if it is a leaf node (i.e. if it has no children). If it is a leaf node, it returns 1, otherwise, it recursively calls itself on the left and right children of the node and returns the sum of the number of leaf nodes in the left and right subtrees.
In the main method, the program creates a binary tree with the given structure and calls the countLeafNodes(Node node) method with the root node as the input. The final output of the program will be the number of leaf nodes in the tree, in this example it will be 3.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment