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 the 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 topic 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 first go through a comprehensive online course on essential Data Structure and Algorithms to at least get an understanding of basic data structures like an 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 the linked list topic we have covered the following coding problems:

• Linked list implementation using generics
• Finding the middle element of the 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 the String algorithm, available here. 

In the future, I am thinking to continue with more tree algorithms and also including some advanced String searching algorithms like Rabin-Karp and Knuth-Morris-Pratt Algorithms. If you have not heard of these algorithms before, I suggest you read 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 printing 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 the 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 the 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 the 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 the 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 than the iterative algorithm, but, even the iterative algorithm is not as tough as the iterative quicksort or iterative post-order traversal algorithm.


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 an 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 it with your friends and colleagues. If you have any questions 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 about what's next, well the master challenge for any serious programmer is to solve data structure and algorithm problems given in the Algorithm Design Manual book by Steven S. Skiena. If you solve those without taking help from the Internet, you will be in a separate league of programmers.