Java program to find the number of Nodes in a Binary Tree

Total number of nodes in a binary tree is known as a size of a tree. We have to write a program in Java to find the total number of nodes in a binary tree. We will create a Node class in Java. Node class will have data, right and left. Data will hold the value of the node. Pointer right and left will hold the address of right and left child respectively.

Write a Program in Java to Find number of nodes of a Tree

We will create a Java program to find the size of a binary tree by calculating the number of nodes in a binary tree.

Find the Size of a Binary Tree

We will use a Queue to implement a Java code. Let’s we have a tree like below. There are total 7 nodes in a binary tree.

Find number of nodes in a binary tree

[vc_row][vc_column width=”2/3″][td_block_text_with_title custom_title=”Method 1″][/td_block_text_with_title][/vc_column][/vc_row]
Write a program in Java to find number of nodes of a tree. Below is the algorithm for method 1.

    1. Insert the root node 1 in the queue
    2. Have a loop till Queue is empty
    3. Remove the element from the queue.
      1. Increment the count
      2. Add the left and right child of the removed element in the queue.

Dry Run Method 1

Steps involved to find the number of nodes of the above binary tree

  1. Take a counter initialized to zero.
  2. If root is not null then add the root in the queue.
  3. Node 1 will be added in the Queue.
  4. Queue is not empty so remove the node from the queue.
  5. We will have Node 1 with us and increment the counter [counter = 1].
  6. If Node 1 has left and right child then add them in the queue.
  7. Node 2 and 3 will get added in the Queue.
  8. Now Queue is not empty so remove the node from the queue
  9. We will get Node 2 with us and increment the counter [counter = 2].
  10. If Node 2 has left and right child then add them in the queue.
  11. Node 4 and 5 will be added in the Queue.
  12. Queue contains currently Node 3, Node 4 and Node 5
  13. Queue is not empty so remove the node from the queue
  14. We will get Node 3 with us. Increment the counter [counter = 3]
  15. If Node 3 has left and right child then add them in the queue.
  16. Node 6 and 7 will get added in the queue.
  17. Queue contains currently Node 4, Node 5, Node 6, Node 7
  18. Queue is not empty so remove the node from the queue.
  19. We will get Node 4. Increment the counter [counter = 4]
  20. If Node 4 has left and right child then add them in the queue.
  21. Nothing will be added in the queue because Node 4 has no children.
  22. Queue is not empty so remove the node from the queue.
  23. We will get Node 5. Increment the counter [counter = 5]
  24. If Node 5 has left and right child then add them in the queue.
  25. Nothing will be added in the queue because Node 5 has no children.
  26. Queue is not empty so remove the node from the queue.
  27. We will get Node 6. Increment the counter [counter = 6]
  28. If Node 6 has left and right child then add them in the queue.
  29. Nothing will be added in the queue because Node 6 has not children.
  30. Queue is not empty so remove the node from the queue.
  31. We will get Node 7. Increment the counter [counter = 7]
  32. If Node 7 has left and right child then add them in the queue.
  33. Nothing will be added in the queue because Node 7 has not children.
  34. Queue is empty so break the loop.
  35. Print the counter which will give the number of nodes in the binary tree.

Here is the Java program for finding the total number of nodes in the binary tree.
[vc_row][vc_column width=”2/3″][td_block_text_with_title custom_title=”Java Program”][/td_block_text_with_title][/vc_column][/vc_row]

import java.util.LinkedList;
import java.util.Queue;
public class NumberOfNodes 
{
	public static class Node {
        String data;
        Node left;
        Node right;

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

    public static class BinaryTree {

        public Node CreateTree()
        {
            Node n1 = new Node("1");
            Node n2 = new Node("2");
            Node n3 = new Node("3");
            Node n4 = new Node("4");
            Node n5 = new Node("5");
            Node n6 = new Node("6");
            Node n7 = new Node("7");

            n1.left = n2;
            n1.right = n3;

            n2.left = n4;
            n2.right = n5;

            n3.left = n6;
            n3.right = n7;

            return n1;
        }

        public void PrintNumberOfNodes(Node root)
        {
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            int num = 0;

            while(!queue.isEmpty())
            {
                Node temp = queue.remove();
                num++;
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
            }
            System.out.println("Number of Nodes are " + num);
        }
    }

    public static void main(String[] args) {

        System.out.println("Creating a Tree");

        BinaryTree bt = new BinaryTree();

        Node root = bt.CreateTree(); //creating a tree

        bt.PrintNumberOfNodes(root);
    }
}

Try It

[vc_row][vc_column width=”2/3″][td_block_text_with_title custom_title=”Conclusion”][/td_block_text_with_title][/vc_column][/vc_row]
Below are the questions asked during interview for which we should provide same solution.

  • number of nodes in a tree
  • number of nodes in a binary tree
  • write a program in java to find number of nodes of a tree
  • Find the size of a binary tree in Java

[vc_row][vc_column width=”2/3″][td_block_text_with_title custom_title=”References”][/td_block_text_with_title][/vc_column][/vc_row]
https://en.wikipedia.org/wiki/Binary_tree

Translate »