Find number of nodes/size of binary tree in java (BFS / example)

• Given a binary tree, count number of nodes using non recursive algorithm.
• We will calculate size of binary tree using breadth first search (bfs) or level order traversal algorithm.
• During binary tree traversal, we will keep on adding the number of elements at each level.
  • At end of traversal, we will get number of nodes in a binary tree.

Algorithm: count number of nodes in a binary tree using java(Fig 1)

• Create local variable nNodes (signify the node count)
  • nNodes initialized to 0
• Visit the Level 0
  • visit all nodes in Level 0 and found only node A
  • nNodes increment by 1 [nNodes = 1]
• Go to Level 1 and visit all nodes in Level 1
  • Found node B,  nNodes increment by 1  [nNodes = 2]
  • Found node C, nNodes increment by 1  [nNodes = 3]
• Go to Level 2 and visit all nodes in Level 2
  • Found node D, nNodes increment by 1 [nNodes = 4]
  • Found node E, nNodes increment by 1  [nNodes = 5]
  • Found node F, nNodes increment by 1   [nNodes = 6]
  • Found node G, nNodes increment by 1 [nNodes = 7]
• Visited all nodes in binary tree [Refer Fig 2]

The time complexity of algorithm is O(n).

Program – number of nodes or size of a binary tree using java (BFS)

1.) CountNodes Class:

• Find number of nodes or size of a binary tree.
• Traverse binary tree using level order traversal.

package org.learn.Question;

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

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

  while (!queue.isEmpty()) {
   Node node = queue.poll();         
   if (node.left != null) {
    queue.offer(node.left);
   }
   if (node.right != null) {
    queue.offer(node.right);
   }
   nNodes++;
  }
  System.out.println("Number of nodes in a binary tree : " + nNodes);
  return nNodes;
 }
}

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 creating a binary tree in main method
• We are calling method of CountNodes class, to find number of nodes in a binary tree.

package org.learn.Client;

import org.learn.Question.CountNodes;
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);

  // 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;

  CountNodes.countNodes(A);
 }
}

Output – Size of binary tree using level order traversal using java

Number of nodes in a binary tree : 7

Download code – size of binary tree non recursive algorithm in java