Find number of nodes/size of a binary tree using 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.

node count binary tree — Fig 1: Node count in a binary tree (BFS)

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]

size binary tree — Fig 2: Node count at each level.

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

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

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

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

1.) CountNodes Class:

2.) Node Class:

3.) App Class:

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

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

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

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

1.) CountNodes Class:

2.) Node Class:

3.) App Class:

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

You may also like: