- 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
Download Code – find number of nodes in binary tree