Number of nodes or size of binary tree in java (DFS / examples)

• Given the binary tree, count number of nodes in a binary tree using recursive algorithm.
• Traverse the binary tree using depth first search (DFS) recursive algorithm.
• We have discussed non recursive (BFS) solution to find number of nodes in a binary tree.

Algorithm – find size or number of nodes in a binary tree

• Given a node of binary tree.
• Find number of children in left subtree. (say nLeftSubtree)
• Find number of children in right subtree.  (say nRightSubtree )
• Total number of nodes (at given node) = nLeftSubtree + nRightSubtree + 1 (given node).

Let us take a couple of examples to understand our problem.

Example 1: find number of nodes in a binary tree

1. Go to Node F
2. Find nodes in Node F’ left subtree. (Node H)
   • We reach Node H
   • Find element in Node H’ left & right subtree
     • Node H is leaf node, so nothing on its left and right subtree
   • Total number of Nodes at Node H = 0 (left subtree) + 0 (right subtree) + 1 (Node H itself).
   • Node H sent count = 1 to its parent node i.e. Node F.
3. Find nodes in Node F’ right subtree.
   • We reach Node I
   • Find element in Node I’ left & right subtree
     • Node I is leaf node, so nothing on its left and right subtree
   • Total number of Nodes at Node I = 0 (left subtree) + 0 (right subtree) + 1 (Node I itself).
   • Node I sent count = 1 to its parent node i.e. Node F.
4. Total Count at Node F = 1 ( left subtree i.e. Node H) + 1 (right subtree ie. Node H) + 1 (Node F itself)
5. Total Count = 3

Example 2: Size of binary tree using recursive algorithm

1. Go to Node C
2. Find the elements in left subtree
   • Apply algorithm of Example 1 on left side.
   • We should get 3 from left side (at Node F)
3. Find the elements in right sub tree
   • Apply algorithm of Example 1 on Node G
   • We should get number of nodes at Node G = 1
4. Receive count 3 from left side and 1 from right side
5. Total count is : 1 (Count for node C) + 3 (nodes in left sub tree) + 1 (nodes in right sub tree)
6. Total Count =5

Example 3: Node count in a binary tree – depth first search

We have demonstrated the execution flow of algorithm in Fig 4. We can analyze it by applying example 1 & example 2.
Time complexity of algorithm is O(n).

Program – number of nodes in a binary tree (recursive algorithm)

1.) NodesInBTree class: NodesInBTree class is responsible for finding number of nodes in a binary tree.

package org.learn.Question;

public class NodesInBTree {
 public static int nodesInBTree(Node root) {
  if(null == root)
   return 0;
  
  int nLeftSubtree = nodesInBTree(root.left);
  int nRightSubtree = nodesInBTree(root.right);
  return nLeftSubtree + nRightSubtree + 1;
 }
}

2.)  Node Class : Node class represents the nodes of 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 binary tree in main method
• We are calling method of NodesInBTree class to get the number of nodes in binary tree.

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.NodesInBTree;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(50);
  // Level 1
  Node B = Node.createNode(30);
  Node C = Node.createNode(90);
  // Level 2
  Node D = Node.createNode(10);
  Node E = Node.createNode(40);
  Node F = Node.createNode(60);
  Node G = Node.createNode(95);
  // Level 2
  Node H = Node.createNode(55);
  Node I = Node.createNode(65);

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

  int nodes = NodesInBTree.nodesInBTree(A);
  System.out.println("Nodes of Binary Tree : " + nodes);
 }
}

Output – Size or number of nodes in a binary tree (Fig 1)

Nodes of Binary Tree : 9

Download Code – find number of nodes in binary tree