Monday, 17 July 2017 03:49

## Write a program to Calculate Size of a tree

Written by
Rate this item

Size of a tree is the number of elements present in the tree. Size of the below tree is 5. Example Tree

Size() function recursively calculates the size of a tree. It works as follows:

Size of a tree = Size of left subtree + 1 + Size of right subtree.

Algorithm:

```size(tree)
1. If tree is empty then return 0
2. Else
(a) Get the size of left subtree recursively  i.e., call
size( tree->left-subtree)
(a) Get the size of right subtree recursively  i.e., call
size( tree->right-subtree)
(c) Calculate size of the tree as following:
tree_size  =  size(left-subtree) + size(right-
subtree) + 1
(d) Return tree_size```
`#include <stdio.h>`
`#include <stdlib.h>`

`/* A binary tree node has data, pointer to left child `
`   ``and a pointer to right child */`
`struct` `node `
`{`
`    ``int` `data;`
`    ``struct` `node* left;`
`    ``struct` `node* right;`
`};`

`/* Helper function that allocates a new node with the`
`   ``given data and NULL left and right pointers. */`
`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);`
`}`

`/* Computes the number of nodes in a tree. */`
`int` `size(``struct` `node* node) `
`{  `
`  ``if` `(node==NULL) `
`    ``return` `0;`
`  ``else`
`    ``return``(size(node->left) + 1 + size(node->right));  `
`}`

`/* Driver program to test size function*/`
`int` `main()`
`{`
`  ``struct` `node *root = newNode(1);`
`  ``root->left        = newNode(2);`
`  ``root->right       = newNode(3);`
`  ``root->left->left  = newNode(4);`
`  ``root->left->right = newNode(5);   `

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

Output:

`Size of the tree is 5` 