How to Count leaf nodes in a binary tree using Recursion in Java
In this post, we will write a Java program to count the leaf nodes in a binary tree. We will use recursion to solve this problem. In a binary tree, each node can have at most two child nodes. A node which has at least one child node is an internal node of the tree. A node which has no left and right subtrees is called a leaf node. So, a leaf node has no child nodes.
Algorithm – Count leaf nodes in a binary tree using Recursion
We will write a recursive program named countLeaves to solve this problem. It takes only one argument which is the root of the binary tree. This function returns an integer value.
- If the node is null then return 0.
- If both the left child and right child of the node is null then return 1. As this node is a leaf node of the tree.
- Call the countLeaves function for the left child of the node.
- Call the countLeaves function for the right child of the node.
- Return the sum of leaf nodes from the left and right subtrees.
Program to count leaf nodes of a binary tree in Java
public class CountLeafNodes { public static void main(String[] args) { /* Tree: 50 / \ 10 20 / \ / \ 30 60 70 80 \ / 40 90 */ TreeNode root = new TreeNode(50); root.left_side_Child = new TreeNode(10); root.right_side_Child = new TreeNode(20); root.left_side_Child.left_side_Child= new TreeNode(30); root.left_side_Child.left_side_Child.right_side_Child = new TreeNode(40); root.left_side_Child.right_side_Child = new TreeNode(60); root.right_side_Child.left_side_Child = new TreeNode(70); root.right_side_Child.right_side_Child = new TreeNode(80); root.right_side_Child.left_side_Child.left_side_Child = new TreeNode(90); System.out.println("No of leaf nodes = " + countLeaves(root)); /* Tree: 50 / \ 10 20 / \ / \ 30 60 70 80 / \ / \ 100 40 90 110 */ TreeNode root1 = new TreeNode(50); root1.left_side_Child = new TreeNode(10); root1.right_side_Child = new TreeNode(20); root1.left_side_Child.left_side_Child = new TreeNode(30); root1.left_side_Child.left_side_Child.left_side_Child = new TreeNode(100); root1.left_side_Child.left_side_Child.right_side_Child = new TreeNode(40); root1.left_side_Child.right_side_Child = new TreeNode(60); root1.right_side_Child.left_side_Child = new TreeNode(70); root1.right_side_Child.right_side_Child = new TreeNode(80); root1.right_side_Child.left_side_Child.l eft_side_Child= new TreeNode(90); root1.right_side_Child.left_side_Child.right_side_Child = new TreeNode(110); System.out.println("No of leaf nodes = " + countLeaves(root1)); } static class TreeNode { int val; TreeNode left_side_Child; TreeNode right_side_Child; TreeNode(int x) { val = x; left_side_Child = null; right_side_Child = null; } } public static int countLeaves(TreeNode node) { if (node == null) { return 0; } if (node.right_side_Child == null && node.left_side_Child == null) { return 1; } int count = 0; count += countLeaves(node.left_side_Child); count += countLeaves(node.right_side_Child); return count; } }
Output:
No of leaf nodes = 4 No of leaf nodes = 6
You can also read:
Leave a Reply