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.

Approach:

1. Initialize height variable to 0.
2. Utilize a Queue data structure similar to Level Order Traversal.
3. At each level, use NULL as a marker to indicate the end of the level.
4. Add the root node to the Queue and also add NULL as the marker for the first level.
5. Dequeue a node from the Queue.
6. If the dequeued node is NULL, it indicates the end of a level or the traversal of the entire tree. Check if the Queue is empty, indicating traversal completion. If not empty, add NULL as a marker for the next level and increment the height by 1.
7. If the dequeued node is not NULL, enqueue its children into the Queue.
8. Repeat steps 5 to 7 until the Queue becomes empty.
9. See the code below for better explanation

Output:

Tree Height 4

Related Problems:

- All N Length Strings from Given String of Length K Medium
- Print All Possible Subsets with Sum equal to a given Number Hard
- Determine If Two Nodes are Cousins Medium
- Backtracking - Rat In A Maze Puzzle Hard