Find the Height of a tree without Recursion
Objective: – Find the Height of a tree without Recursion.
In our earlier post “Height of tree” we had used recursion to find it. In this post we will see how to find it without using recursion.
- 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 to the end of a level OR entire tree is traversed.
- So before adding null as marker for the next level, check if queue is empty, which means we have traveled all the levels and if not empty then add NULL as marker and increase the height by 1.
- If Extracted node in Step 6, is NOT NULL add the children of extracted node to the Queue.
- Repeat Steps from 5 to 8 until Queue is Empty.
- See the Code for better explanation.
Tree Height 4