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..-

Google Microsoft Amazon Facebook more..

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

You may also like...

  • Vijay Kumar

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

%d bloggers like this: