Be the first user to complete this post

  • 0
 Add to List
Medium

Find the Height of a tree without using Recursion

Objective: - Find the Height of a tree without Recursion.

In our earlier post "Height of tree" we used recursion to find it. In this post, we will see how to find it without using recursion.

Approach:

  1. The approach is quite similar to Level Order Traversal which uses Queue.
  2. Take int height =0.
  3. Here we will use NULL as a marker at every level, so whenever we encounter null, we will increment the height by 1.
  4. First, add root to the Queue and add NULL as well as its marker.
  5. Extract a node from Queue.
  6. Check it is NULL, it means either we have reached the end of a level OR the entire tree is traversed.
  7. So before adding null as a marker for the next level, check if the queue is empty, which means we have traveled all the levels and if not empty then add NULL as a marker and increase the height by 1.
  8. If an Extracted node in Step 6, is NOT NULL add the children of the extracted node to the Queue.
  9. Repeat Steps from 5 to 8 until Queue is Empty.
  10. See the Code for a better explanation.

Code:


Output:

Tree Height 4

Also Read: