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