How to Count Number of Leaf Nodes in a Binary Tree in Java - Iterative and Recursive Solution

Hello guys, today I am going to talk about an interesting binary tree-based coding problem from Programming Job interviews. If you have attended a couple of technical interviews then there is a good chance that you already have seen this question about counting a number of leaf nodes in a binary tree. If you know how to solve this problem then it's well and good but if you haven't don't worry, you will learn in this article. If you follow this blog then you might know that I have discussed a lot of data structure and algorithms problems here, including array, linked list, hash table, binary tree, and binary search tree.

If you remember then you can use the same algorithm to count a number of leaf nodes in the binary tree which we have used in the last article, while printing all leaf nodes of a binary tree in Java, using both recursion and iteration.

The logic is the same for the leaf node, any node whose left and right children are null is known as a leaf node in a binary tree. They are the nodes that reside in the last level of a binary tree and they don't have any children. In order to count the total number of leaf nodes in a binary tree, you need to traverse the tree and increase the count variable whenever you see a leaf node.

Since a binary tree is an essential data structure and algorithm topics for programming interviews, it's better to prepare these kinds of questions. I'll show how to solve this using both recursion and iteration in Java in this article.

By the way, if you are not familiar with the binary tree data structure itself, then, I suggest you to first go through a comprehensive course on essential Data Structure and Algorithms like Data Structures and Algorithms: Deep Dive Using Javaon Udemy to at least get an understanding of basic data structures like array, linked list, binary tree, hash tables, and binary search tree. That will help you a lot in solving coding problems

I have also been writing posts about some essential data structure and algorithms for quite some time now and I think it's a good time to just look back on what I have covered so far and what you can expect in the future.

As far as the binary tree is concerned, we have covered the following topics:

• Binary search tree implementation
• PreOrder traversal, both iterative and recursive
• PostOrder traversal
• InOrder traversal
• Algorithm to print all leaves of binary tree

And, on linked list topic we have covered following coding problems:

• Linked list implementation using generics
• Finding the middle element of linked list in one pass
• Algorithm to reverse a linked list
• Finding Nth element from last in a linked list

I have also covered a lot of topics on the array, which you can see here and a lot of topics on String algorithm, available here.

In the future, I am thinking to continue with more tree algorithms and also include some advanced String searching algorithms like Rabin-Karp and Knuth-Morris-Pratt Algorithms. If you not heard of these algorithms before, I suggest you reading Introduction to Algorithms book. One of the classic books to learn data structure and algorithms.

Algorithm to count the number of leaf nodes of binary tree using Recursion

The algorithm to count the total number of leaf nodes is very similar to the earlier problem about theprinting a leaf node.

Here are the actual steps to follow:

1) If the node is null return 0, this is also the base case of our recursive algorithm

2) If a leaf node is encountered then return 1

3) Repeat the process with left and right subtree

4) Return the sum of leaf nodes from both left and right subtree

and here is the sample code based upon above logic

private int countLeaves(TreeNode node) { if (node == null) return 0; if (node.isLeaf()) { return 1; } else { return countLeaves(node.left) + countLeaves(node.right); } }

If you notice this method is private and I have declared this method inside BinaryTree class. In order to access it outside, I have created another method countLeafNodesRecursively() as shown below:

			public int countLeafNodesRecursively() { return countLeaves(root); }

There are two reasons for doing that, the first earlier method expects a starting node, which should be root. It's cleaner for the client to just call this method as root is already available to BinaryTree class. The wrapper method then passes the root to the actual method which counts leaf nodes.

The wrapper method is public so that the client can access it and the actual method is private so that nobody can see it and the developer can change the implementation in the future without affecting clients. This is actually a standard pattern of exposing recursive methods that need a parameter.

Btw, if you understand recursion but struggle to write recursive methods to solve real-world problems like this one, then you should join a good course on Algorithms and Data structure like Algorithms and Data Structures - Part 1 and 2   on Pluralsight, which will not only teach you basics like this but also how to calculate time and space complexity of a particular solution, often needed in a coding interview to prove that your solution passes the performance requirement.

An iterative algorithm to get the total number of leaf nodes of binary tree

The recursive algorithm for counting leaf nodes was pretty easy, so is the iterative algorithm as well. Similar to iterative InOrder traversal example, we have used a Stack to traverse the binary tree. Here are the exact steps of the iterative algorithm to get a total number of leaf nodes of a binary tree:

1) if the root is null then return zero.

2) start the count with zero

3) push the root into Stack

4) loop until Stack is not empty

5) pop the last node and push left and right children of the last node if they are not null.

6) increase the count

At the end of the loop, the count contains the total number of leaf nodes. Here is the sample code based upon the above logic and algorithm:

public int countLeafNodes() { if (root == null) { return 0; } Stack stack = new Stack<>(); stack.push(root); int count = 0; while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); if (node.isLeaf()) count++; } return count; } }

You can see the logic is quite straightforward. The time complexity of this algorithm is O(n) because you need to visit all nodes of the binary tree to count the total number of leaf nodes.

The Stack is a LIFO data structure and we have used the JDK implementation java.util.Stack which also extends the Vector class.

You can further see a good data structure and algorithm books like Grokking Algorithms  by Aditya Bhargava to learn more about Stack and LIFO data structures. Unlike other books, this explains the concept in a much more interesting way and makes this complex topic a bit easier.

Java Program to count the number of leaf nodes in a binary tree

Here is the complete program to count the total number of leaf nodes in a given binary tree in Java. This program demonstrates both recursive and iterative algorithms to solve this problem. In this program, we'll use the following binary tree for testing purposes.

Since there are four leaf nodes in this tree (d, e, g, and h), your program should print 4. The countLeafNodesRecursively() method solves this problem using recursion and countLeafNodes() solves this problem without recursion.

The working of methods is explained in the previous paragraph.

import java.util.Stack; /* * Java Program to count all leaf nodes of binary tree * with and without recursion. * input : a * / \ * b f * / \ / \ * c e g h * / \ * d k * * output: 4 */ public class Main { public static void main(String[] args) throws Exception { // let's create a binary tree BinaryTree bt = new BinaryTree(); bt.root = new BinaryTree.TreeNode("a"); bt.root.left = new BinaryTree.TreeNode("b"); bt.root.right = new BinaryTree.TreeNode("f"); bt.root.left.left = new BinaryTree.TreeNode("c"); bt.root.left.right = new BinaryTree.TreeNode("e"); bt.root.left.left.left = new BinaryTree.TreeNode("d"); bt.root.right.left = new BinaryTree.TreeNode("g"); bt.root.right.right = new BinaryTree.TreeNode("h"); bt.root.right.right.right = new BinaryTree.TreeNode("k"); // count all leaf nodes of binary tree using recursion System.out .println("total number of leaf nodes of binary tree in Java (recursively)"); System.out.println(bt.countLeafNodesRecursively()); // count all leaf nodes of binary tree without recursion System.out .println("count of leaf nodes of binary tree in Java (iteration)"); System.out.println(bt.countLeafNodes()); } } class BinaryTree { static class TreeNode { String value; TreeNode left, right; TreeNode(String value) { this.value = value; left = right = null; } boolean isLeaf() { return left == null ? right == null : false; } } // root of binary tree TreeNode root; /** * Java method to calculate number of leaf node in binary tree. * * @param node * @return count of leaf nodes. */ public int countLeafNodesRecursively() { return countLeaves(root); } private int countLeaves(TreeNode node) { if (node == null) return 0; if (node.isLeaf()) { return 1; } else { return countLeaves(node.left) + countLeaves(node.right); } } /** * Java method to count leaf nodes using iteration * * @param root * @return number of leaf nodes * */ public int countLeafNodes() { if (root == null) { return 0; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); int count = 0; while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); if (node.isLeaf()) count++; } return count; } } Output total number of leaf nodes of a binary tree in Java (recursively) 4 count of leaf nodes of a binary tree in Java (iteration) 4

That's all about how to count the number of leaf nodes in a binary tree in Java. You have learned to solve this problem both by using recursion and iteration. As in most cases, the recursive algorithm is easier to write, read and understand that the iterative algorithm, but, even the iterative algorithm is not as tough as the iterative quicksort or iterative post-order traversal algorithm.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java: An Interview Refresher

Cracking the Coding Interview - 189 Questions with Solutions

Other Array related coding Interview Questions for practice:

• 10 Free Courses to learn Data Structure and Algorithms in Depth [courses]
• TOp 30 linked list coding problems from Interviews (questions)
• How to remove duplicates from an array in Java? [solution]
• 10 Free Data Structure and Algorithms Courses (courses)
• 30+ Array-based Coding Problems from Interviews (questions)
• How to check if an array contains a number in Java? [solution]
• Free Data Structure and Algorithms Courses for Programmers (courses)
• Write a program to find the missing number in integer array of 1 to 100? [solution]
• How do you reverse an array in place in Java? [solution]
• 50+ Data Structure and Algorithms Coding Problems from Interviews (questions)
• 10 Algorithms Books Every Programmer should read [books]
• 10 Algorithms courses to Crack Coding Interviews [courses]

Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any question or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.

P. S. If you are thinking what's next, well the master challenge for any serious programmer is to solve data structure and algorithm problems given in Algorithm Design Manualby Steven S. Skiena. If you solve those without taking help from the Internet, you will be in a separate league of programmers.