# Program to calculate the size of a tree

## Size of a tree is nothing but the number of nodes present in the tree.

Below algorithm finds the size of a tree recursively ie, size of a tree = size of a leftsubtree + 1 + size of a right subtree.  For each Node, size() function calculates the size of the leftsubtree and rightsubtree and adds 1, to include the present node.

## Algorithm

Time Complexity: O(n),

Same as Tree Traversal

1. If the tree is empty return 0
2. else,
a. return size of the tree ie, (size(Node->left)+ 1 + size(Node->right))
In return statement we are calling the size of the left subtree recursively ie, size(Node->left)
In return statement we are calling the size of right subtree recursively ie, size(Node->right)

## C++ Program

#include<iostream>
using namespace std;

struct Node  //Defining a Node
{
char data;
Node* left;
Node* right;
};

Node* newNode(char data){  //Creating a Node with left and right pointers pointing to NULL
Node* node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int size(Node* node) //Function which returns the size of the tree
{
if(node!=NULL) //For each node calculate the size of left subtree and right subtree
{
return(size(node->left)+1+size(node->right)); //Size of tree= Size of leftsubtree + 1 + Size of right subtree
}
else
{
//cout<<"hi";
return 0; //If there is no node return 0 as the size
}

}
int main()
{
Node* root = newNode('A');  //Assigning the Node values
root->left = newNode('B');
root->right = newNode('C');
root->left->left = newNode('D');
root->left->right = newNode('E');
root->right->left = newNode('F');
cout<<"size of the tree is "<<size(root); //Printing the size of the tree
return 0;

}

Scroll to Top