# Program to Calculate Size of a Binary Tree

• Write a C program to find the total number of nodes in a binary tree.
• Function to print size of a binary tree.

To find the size of a binary tree, we have to count the total number of nodes in a binary tree. For Example:

```Given Binary Tree
1  <--Root
/ \
2    3
/ \    \
4  5     6
Size of Binary Tree : 6
```
In this program, we will use recursion to find the size of a binary tree. Finding the size of binary tree can be divided to two sub problems of finding the size of left and right sub tree.

Size of Tree = Size of Left Sub Tree + 1 + Size of Right Sub Tree;

Algorithm to find size of a binary tree
Let "node" be the pointer to a tree node and getSizeOfTree function returns size of tree.
• If node is NULL(Empty tree), then return 0.
• Find the total number of nodes in left sub tree by recursively calling getSizeOfTree for left sub tree(getSizeOfTree(node->left)). Let it be leftTreeSum.
• Find the total number of nodes in right sub tree by recursively calling getSizeOfTree for right sub tree(getSizeOfTree(node->right)). Let it be rightTreeSum.
• Return (leftTreeSum + 1 + rightTreeSum).

In this program, we will write a recursive function "getSizeOfTree" which takes a node pointer as input and returns size of the tree by implementing above algorithm.

```int getSizeOfTree(struct node *root){
if(root == NULL)
return 0;
return getSizeOfTree(root->left) + 1 + getSizeOfTree(root->right);
}
```

## C program to print alternate nodes of a singly linked list

```#include <stdio.h>

struct node {
int data;
struct node *left;
struct node *right;
};

struct node* getNewNode(int data) {
/* dynamically allocate memory for a new node */
struct node* newNode =
(struct node*)malloc(sizeof(struct node));

/* populate data in new Node */
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

/*
This function returns following tree
1
/ \
2    3
/ \  / \
4  5 6  7
*/
struct node* generateBTree(){
// Root Node
struct node* root =  getNewNode(1);
// Level 2 nodes
root->left = getNewNode(2);
root->right = getNewNode(3);
// Level 3 nodes
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
root->right->right = getNewNode(7);

return root;

}
/*
Returns total number of nodes(size) in a bianry tree
getSizeOfTree(root) = getSizeOfTree(left-subTree) + 1
+ getSizeOfTree(right-subTree);
*/
int getSizeOfTree(struct node *root){
if(root == NULL)
return 0;
return getSizeOfTree(root->left) + 1 + getSizeOfTree(root->right);
}

int main() {
struct node *root = generateBTree();

printf("Size of Tree = %d", getSizeOfTree(root));

getchar();
return 0;
}
```
Output
```Size of Tree = 7
```