Description: Size of a tree is the number of elements in the tree. Given a tree, we have to calculate the size of the tree, that is the number of elements.

 
If video does not load, Click here
 
Example:

The tree below contains 5 elements.

Algorithm and implementation:

/*Recursive algorithm to solve the problems is:*/

int size(node *root)

{

if(root==NULL)

return 0;/*tree is empty*/

else

return (size(root->left) +size(root->right) + 1 );/*size of left subtree+right subtree+1*/

}

 
Time Complexity:

O(n) where n is the number of elements in the tree.

Go to top