Find number of leaf nodes in a binary tree (Java/ BFS /example)

  • Given a binary tree, count number of leaf nodes in a binary tree using non recursive method.
    • Traverse the binary tree using level order traversal or breadth first search (bfs).
  • What is leaf node in binary tree?
    A node in a binary tree, which does not have any children (left & right node) is called leaf node

Similar problems – Count leaf nodes in a binary tree

leaf node binary tree recursive
Fig 1: Count leaf nodes in binary tree

Example & Algorithm to find leaf nodes in a binary tree using java

  • Create nLeaves variable, number of leaf nodes in binary tree.
  • Traverse the binary tree using level order traversal or BFS
  • Visit the Level 0
    • Node A is non leaf node & nLeaves will be remain 0
  • Go to Level 1  & visit all nodes.
    • Node B & Node C are non leaf nodes
      • nLeaves will remain 0
  • Go to Level 2  & visit all nodes.
    • Visit Node D, which is leaf node (as both left & right child is null)
      • nLeaves increment by 1, nLeaves becomes 1
    • Visit Node E is leaf node
      • nLeaves increment by 1 so nLeaves becomes 2
    • Visit Node F & Node G, which are non leaf node
      • nLeaves will remain 2
  • Similarly visit the Level 3
    • At level 3, All nodes H, I, J, K are leaf nodes
      • nLeaves will become 6
  • Number of leaf nodes in a binary tree = 6
level leaf count tree bfs
Fig 2: Leaf count at each level

Time complexity of algorithm is O(n).

Program: count number of leaf nodes in a binary tree using java

1.) CountLeaves Class:

  • CountLeaves class is responsible for finding the number of leaf nodes in binary tree.
  • We will traverse the binary tree using level order traversal or breadth first search (BFS) algorithm.
package org.learn.Question;

import java.util.LinkedList;
import java.util.Queue;

public class CountLeaves {
 public static int countLeaves(Node root) {
  if (root == null) {
   System.out.println("Tree is empty");
   return -1;
  }
  int nLeaves = 0;
  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);

  while (!queue.isEmpty()) {
   Node node = queue.poll();

   if (node.left == null && node.right == null) {
    nLeaves++;
    continue;
   }
   if (node.left != null) {
    queue.offer(node.left);
   }
   if (node.right != null) {
    queue.offer(node.right);
   }
  }
  System.out.println("Number of leaf nodes in a binary tree: " + nLeaves);
  return nLeaves;
 }
}

2.) Node Class:

  • Node class is representing the nodes of a binary tree.
package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

  • We are constructing the binary tree in a main method.
  • We are calling method of CountLeaves class to calculate number of leaf nodes in a binary tree.
  • We will traverse the binary tree using recursive algorithm.
package org.learn.Client;

import org.learn.Question.CountLeaves;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {

  // root level 0
  Node A = Node.createNode(55);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(40);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(80);
  Node F = Node.createNode(45);
  Node G = Node.createNode(90);

  // Level 3
  Node H = Node.createNode(10);
  Node I = Node.createNode(35);
  Node J = Node.createNode(65);
  Node K = Node.createNode(75);

  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;
  // connect level 2 and level 3
  F.left = H;
  F.right = I;
  G.left = J;
  G.right = K;

  CountLeaves.countLeaves(A);
 }
}

Output: number of leaf nodes using breadth first algorithm in java

Number of leaf nodes in a binary tree: 6

Download Code – count leaf nodes in binary tree (bfs)

 

Scroll to Top