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

• Count non leaf nodes in a binary tree.
• Count non leaf nodes having on child node (left or right child).
• Count non leaf nodes in a binary tree having both left & right child node.

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

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)