Given a binary tree write a C program to count size of binary tree.

For example the size of  binary tree is 4 in below binary tree.

```            (3)
/  \
(5)  (6)
/
(2)```

C program to count size of binary tree

```#include<stdio.h>
#include<malloc.h>

typedef struct node
{
int value;
struct node* left;
struct node* right;
}Tree;

Tree* make_node(int value)
{
Tree* newNode = (Tree*) malloc(sizeof(Tree));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

void free_memory(Tree* root)
{
if(root == NULL) return;
free_memory(root->left);
free_memory(root->right);
free(root);
}

Tree* insert(Tree* root, int value)
{
if (root == NULL) return root = make_node(value);

else
{
if(!root->left) root->left = insert(root->left, value);
else
root->right = insert(root->right, value);
}

return root;
}

// recursive method to count size of binary tree
int size_of_tree(Tree* root)
{
// Base condition, if node is null return 0
if (root == NULL) return 0;

return 1 + size_of_tree(root->right) + size_of_tree(root->left);
}

int main()
{
Tree* root = NULL;
root = insert(root, 3);
insert(root, 5);
insert(root, 6);
insert(root, 2);

int size = size_of_tree(root);

printf("Size of Tree is %d\n",size);

// deallocate memory
free_memory(root);

return 0;
}
```

output: Size of Tree is 4

How it works

```// recursive method to count size of binary tree
int size_of_tree(Tree* root)
{
// Base condition, if node is null return 0
if (root == NULL) return 0;

return 1 + size_of_tree(root->right) + size_of_tree(root->left);
}```
• The total number of nodes in a binary tree is the number of nodes in the root’s left subtree, plus the number of nodes in its right subtree, plus one.