Be the first user to complete this post
|Add to List
131. 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.
- The approach is quite similar to Level Order Traversal which uses Queue.
- Take int height =0.
- Here we will use NULL as a marker at every level, so whenever we encounter null, we will increment the height by 1.
- First, add root to the Queue and add NULL as well as its marker.
- Extract a node from Queue.
- Check it is NULL, it means either we have reached the end of a level OR the entire tree is traversed.
- 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.
- If an Extracted node in Step 6, is NOT NULL add the children of the extracted node to the Queue.
- Repeat Steps from 5 to 8 until Queue is Empty.
- See the Code for a better explanation.
Tree Height 4