Search Your Topic

config
Monday, 17 July 2017 03:49

Write a program to Calculate Size of a tree

Written by
Rate this item
(0 votes)

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

Example Tree

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
Read 95 times
Anish Sir

"I am delighted once again to pen the welcome note to the Tosh!Yas Technologies ."

 Call +91 74 88 34 7779  | Email : anishsingh@live.com

toshiyas.in

Leave a comment

Make sure you enter all the required information, indicated by an asterisk (*). HTML code is not allowed.