Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the Height of a tree without Recursion

Objec­tive: - Find the Height of a tree with­out Recursion.

In our ear­lier post “Height of tree” we had used recur­sion to find it. In this post we will see how to find it with­out using recursion.

Approach:

  1. Approach is quite sim­i­lar to Level Order Tra­ver­sal which uses Queue.
  2. Take int height =0.
  3. Here we will use NULL as a marker at every level, so when­ever we encounter null, we will incre­ment 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 to the end of a level OR entire tree is traversed.
  7. So before adding null as marker for the next level, check if queue is empty, which means we have trav­eled all the lev­els and if not empty then add NULL as marker and increase the height by 1.
  8. If Extracted node in Step 6, is NOT NULL add the chil­dren of extracted node to the Queue.
  9. Repeat Steps from 5 to 8 until Queue is Empty.
  10. See the Code for bet­ter explanation.

Code:


Out­put:

Tree Height 4

You may also like...