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:

- Convert BST to Greater Sum Tree Medium
- Find all subsets of size K from a given number N (1 to N) Medium
- AVL Tree - Insertion Hard
- In a number, add digits until it becomes a single digit Beginner
- Generate All Balanced Parentheses Combinations (N Pairs) Medium