Home Trees Find the height of the binary tree without using recursion.

Find the height of the binary tree without using recursion.

by nikoo28
0 comment

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

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

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

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

0 comment

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