Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Size of Tree

Last Updated on March 25, 2022 by Ria Pathak

BFS , Recursion

Easy

### Problem Statement :

Given a binary tree, our task is to print the size of the tree. Size of tree represented as the number of nodes in the given tree.

See original problem statement here

### Solution Approach :

#### Introduction :

The size of the tree is the total count of the nodes present in the tree. Total nodes present is the sum of the count of nodes present in left & right subtree plus `1` (root node).

#### Method 1(using Queue):

We can use a queue to perform level order traversal. We will perform following operations :

1. Create an empty queue q and a counter to store the size.
2. push the root node into the queue `(q.push(root))` and do following while `q` is not empty:
• pop the front element of queue (`temp=q.front()`).
• if `temp->left` & `temp->right` is not NULL, push them into the `q`.
• Increment the counter every time we push a node, by `1`.
3. Return counter.

#### Method 2 (Recursion) :

Introduction says it all, all we need is to store the count of left subtree & right subree recursively.
Now we will increment our sum by `1` to count the root node.
We will do the same for left & right subtrees by recursively calling , `root->left` & `root->right`.

### Solutions:

```#include <stdio.h>

#include<stdlib.h>

#define ll long long

#define REP(i, n) for (i = 0; i < n; i++)

struct nodelist

{

ll value;

struct nodelist *left;

struct nodelist *right;

};

typedef struct nodelist node;

struct Queue

{

int front, rear, size;

unsigned capacity;

node* *array;

};

typedef struct Queue queue;

queue* createQueue(unsigned capacity)

{

queue* qu =(queue*)malloc(sizeof(queue));

qu->capacity = capacity;

qu->front = qu->size =0;

qu->rear = capacity-1;

qu->array = (node **)malloc(qu->capacity * sizeof(node));

return qu;

}

int isFull(queue*  queue1)

{

return (queue1->size == queue1->capacity);

}

int isEmpty(queue* queue1)

{

return (queue1->size==0);

}

void enqueue(queue* queue1, node* item)

{

if(isFull(queue1))

return ;

queue1->rear = (queue1->rear +1 )%queue1->capacity;

queue1->array[queue1->rear] = item;

queue1->size = queue1->size +1;

}

node dequeue(queue* queue1)

{

node* item = queue1->array[queue1->front];

queue1->front = (queue1->front +1)%queue1->capacity;

queue1->size = queue1->size -1;

return *item;

}

node* front(queue* queue1)

{

return queue1->array[queue1->front];

}

node* rear(queue * queue1)

{

return queue1->array[queue1->rear];

}

node *createNode(ll value)

{

node *t= (node *) malloc(sizeof(node));

t->value = value;

t->right = t->left = NULL;

return  t;

}

void deleteNode(node*t)

{

free(t);

}

node *replaceNegativeOne(node *root)

{

if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))

return NULL;

root->left = replaceNegativeOne(root->left);

root->right = replaceNegativeOne(root->right);

return root;

}

void deleteTree(node *node1)

{

if(node1==NULL)

return;

deleteTree(node1->left);

deleteTree(node1->right);

free(node1);

}

node *createTreeByLevelTree()

{

ll n,m;

queue* queue1 = createQueue(100000);

node *root, *t;

root = NULL;

while(scanf("%lld", &n))

{

if(isEmpty(queue1))

{

root= createNode(n);

enqueue(queue1,root);

continue;

}

scanf("%lld", &m);

t = front(queue1);

dequeue(queue1);

t->left =createNode(n);

t->right=createNode(m);

if(t->left->value !=-1)

enqueue(queue1,t->left);

if(t->right->value !=-1)

enqueue(queue1,t->right);

if(isEmpty(queue1))

break;

}

return root;

}

int calculateSize(node *t)

{

if(t == NULL)

return 0;

return 1+calculateSize(t->left) + calculateSize(t->right);

}

int main() {

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

printf("%d ",calculateSize(root));

deleteTree(root);

return 0;

}
```
```#define REP(i, n) for (i = 0; i < n; i++)

#define pb(a) push_back(a)

#define vi vector<long>

#define ll long long

#include <bits/stdc++.h>

using namespace std;

struct node

{

ll value;

node *left;

node *right;

};

node *createNode(ll value)

{

node *t = new node();

t->value = value;

t->right = t->left = NULL;

return t;

}

void deleteNode(node *t)

{

delete t;

}

node *replaceNegativeOne(node *root)

{

if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))

return NULL;

root->left = replaceNegativeOne(root->left);

root->right = replaceNegativeOne(root->right);

return root;

}

node *createTreeByLevelTree()

{

ll n, m;

queue<node *> q;

node *root, *t;

root = NULL;

while (cin >> n)

{

if (q.empty())

{

root = createNode(n);

q.push(root);

continue;

}

cin >> m;

t = q.front();

q.pop();

t->left = createNode(n);

t->right = createNode(m);

if (t->left->value != -1)

{

q.push(t->left);

}

if (t->right->value != -1)

{

q.push(t->right);

}

}

return root;

}

void deleteTree(node *node)

{

if (node == NULL)

return;

deleteTree(node->left);

deleteTree(node->right);

delete node;

}

int calculateSize(node* root)

{

if(root == NULL)

return 0;

queue<node *> q;

int count = 1;

q.push(root);

while(!q.empty())

{

node *temp = q.front();

if(temp->left)

{

q.push(temp->left);

count++;

}

if(temp->right)

{

q.push(temp->right);

count++;

}

q.pop();

}

return count;

}

int main()

{

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

cout<< calculateSize(root)<<endl;

deleteTree(root);

return 0;

}
```
```

import java.util.*;

import java.util.Scanner;

import java.io.*;

class Node

{

long value;

Node left, right;

public Node(long item)

{

value = item;

left = right = null;

}

}

class BinaryTree {

Node root;

BinaryTree() {

root = null;

}

Node createNode(long value) {

Node t = new Node(value);

return t;

}

Node replaceNegativeOne(Node root) {

if (root == null || (root.value == -1 && root.left == null && root.right == null)) {

return null;

}

root.left = replaceNegativeOne(root.left);

root.right = replaceNegativeOne(root.right);

return root;

}

Node createTreeByLevelTree() {

Scanner sc = new Scanner(System.in);

long n, m;

Node t;

root = null;

while (sc.hasNext()) {

n = sc.nextLong();

if (queue.isEmpty()) {

root = createNode(n);

continue;

}

m = sc.nextLong();

t.left = createNode(n);

t.right = createNode(m);

if (t.left.value != -1)

if (t.right.value != -1)

if (queue.isEmpty())

break;

}

return root;

}

void deleteTree(Node node) {

node = null;

}

int calculateSize(Node node) {

if(node == null)

return 0;

return 1+calculateSize(node.left)+calculateSize(node.right);

}

}

public class Main {

public static void main(String[] args) {

BinaryTree bt = new BinaryTree();

bt.root = bt.createTreeByLevelTree();

bt.root = bt.replaceNegativeOne(bt.root);

System.out.println(bt.calculateSize(bt.root));

bt.deleteTree(bt.root);

}

}
```

[forminator_quiz id="1772"]

This article tried to discuss BFS , Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on BFS , Recursion you can check out MYCODE | Competitive Programming.