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

Yogesh

9 years ago

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

Go to Node F
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.
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.
Total Count at Node F = 1 ( left subtree i.e. Node H) + 1 (right subtree ie. Node H) + 1 (Node F itself)
Total Count = 3

Example 2: Size of binary tree using recursive algorithm

Go to Node C
Find the elements in left subtree
- Apply algorithm of Example 1 on left side.
- We should get 3 from left side (at Node F)
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
Receive count 3 from left side and 1 from right side
Total count is : 1 (Count for node C) + 3 (nodes in left sub tree) + 1 (nodes in right sub tree)
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