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

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 same for leaf node, any node whose left and right children is null is known as leaf node in binary tree. They are the nodes which resides in the last level of binary tree and they don't have any children. In order to count total number of leaf nodes in binary tree, you need to traverse the tree and increase the count variable whenever you see a leaf node. Since binary tree is an essential data structure and algorithm topics for programming interviews, its better to prepare these kind of questions. I'll show how to solve this using both recursion and iteration in Java in this article.

I have 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 future. As far as the binary tree is concerned, we have covered following topics:



and on linked list topic we have covered


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 future, I am thinking to continue with more tree algorithms and also include some advanced String searching algorithms e.g. Rabin-Karp and Knuth-Morris-Pratt Algorithms. If you not heard of this algorithms before, I suggest you reading Introduction to Algorithms book. One of the classic book to learn data structure and algorithms. 



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

The algorithm to count a total number of leaf nodes is very similar to the earlier problem about printing leaf node. Here are the actual steps to follow:

1) if node is null return 0, this is also the base case of our recursive algorithm
2) if 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 countLeafNodesRecursivel() as shown below:

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

There are two reason for doing that, first earlier method expect a starting node, which should be root. It's cleaner for client to just call this method as root is already available to BinaryTree class. The wrapper method then pass the root to the actual method which counts leaf nodes. The wrapper method is public so that client can access it and actual method is private so that nobody can see it and developer can change the implementation in future without affecting clients. This is actually standard pattern of exposing recursive methods which need a parameter.

Btw, if you understand recursion but struggle to write recursive methods to solve real world problems e.g. this one, then you should read Grokking Algorithms, a new data structure and algorithm book which explains the concept in a much more interesting way then other books.

How to Count Number of Leaf Nodes in Binary Tree using recursion


Iterative algorithm to get total number of leaf nodes of binary tree

The recursive algorithm for counting leaf nodes was pretty easy, so is 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 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 a 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. See a good data structure and algorithm books like Introduction to Algorithms to learn more about Stack and LIFO data structures.

How to Count Number of Leaf Nodes in Binary Tree without recursion



Java Program to count number of leaf nodes in binary tree

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

How to Count Number of Leaf Nodes in Binary Tree


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 touch as the iterative quicksort or iterative post-order traversal algorithm.

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


No comments :

Post a Comment