# 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:

1. Approach is quite similar to Level Order Traversal which uses Queue.
2. Take int height =0.
3. Here we will use NULL as a marker at every level, so whenever we encounter null, we will increment 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 traveled all the levels 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 children of extracted node to the Queue.
9. Repeat Steps from 5 to 8 until Queue is Empty.
10. See the Code for better explanation.

Code:

Output:

```Tree Height 4
```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

### 1 Response

1. Vijay Kumar says:

package datastructues;

import java.util.Queue;

public class TreeHeight {
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.left.left.right = new Node(8);

TreeHeight i = new TreeHeight();
System.out.println(“Tree Height ” + i.getHeight(root));

}

private int getHeight(Node root) {
int height = 1;
while(! a.isEmpty())
{
Node poll = a.poll();
if(poll.left == null && poll.right == null)
{
height++;
}

}
return height;
}
}

class Node {
int data;
Node left;
Node right;

public Node(int data) {
this.data = data;
}
}

This site uses Akismet to reduce spam. Learn how your comment data is processed.