Program to calculate the size of a tree

Size of a tree is nothing but the number of nodes present in the tree.

Below algorithm finds the size of a tree recursively ie, size of a tree = size of a leftsubtree + 1 + size of a right subtree.  For each Node, size() function calculates the size of the leftsubtree and rightsubtree and adds 1, to include the present node.

Example

Algorithm

Time Complexity: O(n),

Same as Tree Traversal

1. If the tree is empty return 0
2. else,
    a. return size of the tree ie, (size(Node->left)+ 1 + size(Node->right))
    In return statement we are calling the size of the left subtree recursively ie, size(Node->left)
    In return statement we are calling the size of right subtree recursively ie, size(Node->right)

C++ Program

#include<iostream>
using namespace std;

struct Node  //Defining a Node
{
	char data;
	Node* left;
	Node* right;
};

Node* newNode(char data){  //Creating a Node with left and right pointers pointing to NULL
	Node* node = new Node();
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}
int size(Node* node) //Function which returns the size of the tree
{
	if(node!=NULL) //For each node calculate the size of left subtree and right subtree 
	{
		return(size(node->left)+1+size(node->right)); //Size of tree= Size of leftsubtree + 1 + Size of right subtree
	}
	else			
	{
		//cout<<"hi";
		return 0; //If there is no node return 0 as the size
	}

}
int main()
{
	Node* root = newNode('A');  //Assigning the Node values
	root->left = newNode('B');
	root->right = newNode('C');
	root->left->left = newNode('D');
	root->left->right = newNode('E');
	root->right->left = newNode('F');	
	cout<<"size of the tree is "<<size(root); //Printing the size of the tree
	return 0;

}
Try It


Next > < Prev
Scroll to Top