# 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:

#### 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