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.

by nikoo28
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
sample_treeOutput: 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

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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