*832*

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

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