Find Size of Binary Tree in C

Size of Binary Tree

 

Size of Binary tree is defined as the number of nodes in the given tree. It can be easily calculated using recursion and tree traversals. In this article this problem is solved using recursion.

size of binary tree

Algorithm :

  • If node is empty, return NULL.
  • Otherwise, recursively call the size function for the left and right subtree.
  • Return 1 + sum of left and right subtree.
size of binary tree in c

Code in C based on above ALgorithm

#include <stdio.h>
#include <stdlib.h>

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


struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

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

int main()
{
struct node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);

printf("Size of the tree is %d", size(root));
getchar();
return 0;
}
Output :


Size of the tree is 5