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.


Given this Binay Tree as input:

           /     \        
          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
    2. Find the size of the right subtree
    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;
   return temp;

/*The function that returns the number of nodes
int the tree*/
int size(node *root)
   /*Base case when the tree is NULL*/
      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
           /     \        
          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;


Size of the tree is 

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