Find the height of the binary tree without using recursion.

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

Input: Sample Tree (Pointer to node 1 is given).
Output: 3

We discussed the recursive method to find the height of the binary tree in this post-

• Find the height of the binary tree

The non-recursive method will definitely require the level order traversal technique. The level order traversal will traverse the above tree in following manner-

• 1
• 2, 3
• 4, 5

If we are able to keep a track for end of each level, we can easily get the number of levels after the complete traversal. The level 1, is over as soon as we traverse the root node. Insert a NULL in the queue after that. A NULL indicates the end of a level. For better understanding observe the algorithm below-

int heightOfBinaryTree(struct binaryTreeNode * root)
{
	// Level order traversal
	struct binaryTreeNode * temp = NULL;
	struct queue * Q = NULL;
	
	// Maintain a level count
	int level = 0;

	if(root == NULL)
		return 0;

	Q = enQueue(Q, root);
	// Now the first level will end over here,
	// So append a NULL node
	Q = enQueue(Q, NULL);
	
	while(!isQueueEmpty(Q))
	{
		temp = Q -> front -> data;
		Q = deQueue(Q);
		
		// If we encounter a NULL, that means an end of a level
		// And we need to increment the level count
		if(temp == NULL)
		{
			// Put the marker for next level also
			if(!isQueueEmpty(Q))
				Q = enQueue(Q, NULL);
			
			level++;
		}
		else
		{
			// We continue with the level order traversal
			if(temp -> left)
				Q = enQueue(Q, temp -> left);
			if(temp -> right)
				Q = enQueue(Q, temp -> right);
		}
	}
	// Delete the queue
	free(Q);
	
	// Now return the count
	return level;
}

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

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