*679*

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