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

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

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

Similar problems – Count leaf nodes in a binary tree

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

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

1.) CountLeaves Class:

2.) Node Class:

3.) App Class:

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

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

Similar problems – Count leaf nodes in a binary tree

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

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

1.) CountLeaves Class:

2.) Node Class:

3.) App Class:

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

You may also like: