- 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 : 6In 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