Home Trees Write an algorithm to find the size of a binary tree without using recursion.

# Write an algorithm to find the size of a binary tree without using recursion.

0 comment

Question: Given the root pointer to a binary tree, find its size.

Input: Sample Tree (Pointer to node 1 is given). Find the size
Output: Size = 7

We discussed how to find the size of a binary tree using the recursive method in this post:-

This technique involved recursion and the understanding can be a bit complicated. If you prefer to go through the iterative way, we can simple do a level order traversal on the tree. At the time of printing the node, if we increment a counter variable, that will give us the number of total nodes in the end. So with a simple modification, we can write the code as:-

#include<stdio.h>

struct binaryTreeNode{
int data;
struct binaryTreeNode * left;
struct binaryTreeNode * right;
};

// Iterative method to find the size of a binary tree
// FInding the number of nodes
int sizeOfBinaryTree(struct binaryTreeNode * root)
{
// Counter variable to store the number of nodes
int count = 0;

// Level order traversal
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;
if(root == NULL)
return 0;

Q = enQueue(Q, root);
while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;
Q = deQueue(Q);

// We increment the counter here
count++;

if(temp -> left)
Q = enQueue(Q, temp -> left);
if(temp -> right)
Q = enQueue(Q, temp -> right);
}
free(Q);

return count;
}


Time Complexity:- O(n)
Space Complexity:- O(n)

Ideone link for running code:- http://ideone.com/UgS9nO

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More