Size of a Binary Tree

By | October 16, 2015

Size of a Binary Tree

Given a binary tree, we need to print the size of the Binary tree, i.e. the number of nodes present in it.

Example:

Given this Binay Tree as input:

             80                 
           /     \        
          60      110     
         /  \    /  \     
       35   40  85   130

For this tree shown above the answer should be 7.

Size of a tree= Size of the left subtree + 1 + Size of the right subtree.

size() is a recursive function that return the size of the tree.

Finding the size of a Binary Tree solution:

Video Explanation to find the size of the Binary Tree:

Algorithm to find size of a Binary Tree :

  1. If the root is null ( the tree is empty) then return 0.
  2. Else
    1. Find the size of the left subtree
      size(root->left).
    2. Find the size of the right subtree
      size(root->right).
    3. Return size(root->left) + size(root->right) + 1

Size of Binary Tree solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure for each node of the tree*/
struct node
{
   int data;
   node *right,*left;
};


/*Function that allocates memory for
each new node and initialises it*/
node * newNode(int data)
{
   node *temp=new node;
   temp->data=data;
   temp->left=NULL;
   temp->right=NULL;
   
   return temp;
}

/*The function that returns the number of nodes
int the tree*/
int size(node *root)
{
   /*Base case when the tree is NULL*/
   if(!root)
      return 0;
   /*Calculating recursively for left subtree
   right subtree and adding 1 to it for present node*/	
   return (size(root->left) + size(root->right) +1);
}

int main()
{
  /*        
  We are making the following tree
  			  80                 
           /     \        
          60      110     
         /  \    /  \     
       35   40  85   130
  This is a BST.
  */
  node *root         = newNode(80);
  root->left         = newNode(60);
  root->right        = newNode(110);
  root->left->left   = newNode(35);
  root->left->right  = newNode(40);   
  root->right->left  = newNode(85);  
  root->right->right = newNode(130);  
  
  cout<<"Size of the tree is \n"<<size(root);  
  
  return 0;
}

Output:

Size of the tree is 
7

Time Complexity: O(N) as all nodes are visited once