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

- Approach is quite similar to
which uses**Level Order Traversal**.**Queue** - Take int
=0.**height** - 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
and add NULL as well as its marker.**Queue** - 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.

**Code:**

import java.util.LinkedList; | |

import java.util.Queue; | |

public class T_TreeHeightWithOutrecursion { | |

// use NULL as a marker at every level, so whenever we encounter null, we | |

// will increment the height by 1 | |

public int getHeight(Node root) { | |

Queue<Node> q = new LinkedList<Node>(); | |

int height = 0; | |

// add root to the queue | |

q.add(root); | |

// add null as marker | |

q.add(null); | |

while (q.isEmpty() == false) { | |

Node n = q.remove(); | |

// check if n is null, if yes, we have reached to the end of the | |

// current level, increment the height by 1, and add the another | |

// null as marker for next level | |

if (n == null) { | |

// before adding null, check if queue is empty, which means we | |

// have traveled all the levels | |

if(!q.isEmpty()){ | |

q.add(null); | |

} | |

height++; | |

}else{ | |

// else add the children of extracted node. | |

if (n.left != null) { | |

q.add(n.left); | |

} | |

if (n.right != null) { | |

q.add(n.right); | |

} | |

} | |

} | |

return height; | |

} | |

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); | |

T_TreeHeightWithOutrecursion i = new T_TreeHeightWithOutrecursion(); | |

System.out.println("Tree Height " + i.getHeight(root)); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

} | |

} |

**Output**:

Tree Height 4

package datastructues;

import java.util.LinkedList;

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) {

Queue a = new LinkedList();

a.add(root);

int height = 1;

while(! a.isEmpty())

{

Node poll = a.poll();

if(poll.left == null && poll.right == null)

{

height++;

}

if(poll.left != null) a.add(poll.left);

if(poll.right != null) a.add(poll.right);

}

return height;

}

}

class Node {

int data;

Node left;

Node right;

public Node(int data) {

this.data = data;

}

}