The algorithm works as follows:

• Each node starting from the parent node is push into an stack. Then the element is popped from the stack and a check is made to find whether the node has left and right child. If any one or both are present the elements are pushed into stack. At the same time a corresponding entry is made into a map with key as ‘node’ and value as the ‘height’ .The value of height is one more than the height of parent and intial height of parent is set to 1.

The code flow is explained below.

• The program contains two classes : Node and BinaryTree class. The Node class is a datastructure used to build a tree and BinaryTree is a class to find the height.
• The class Node is a data structure which can have left child (Node), a right child (Node) and can contain any value.

package com.src;

public class Node {

 

private Node left;

private Node right;

private Object value;

 

public Node getLeft() {

return left;

}

 

public Node getRight() {

return right;

}

 

public Object getValue() {

return value;

}

 

public Node(Node left, Node right, Object value) {

super();

this.left = left;

this.right = right;

this.value = value;

}

}

 

The BinaryTree class contains the logic of finding the height of the tree.

Consider the following example:

• The createTree() method is used to create the node for each element in tree. Create node starting from the leaf node and moving upward. For above tree:

Node node21 = new Node(null,null,21);

Node node1 = new Node(null,node21,1);

• For the given example the createTree() method will have code as:

private void createTree(){

Node node21 = new Node(null,null,21);

 

Node node23 = new Node(null,null,23);

Node node56 = new Node(null,null,56);

Node node11 = new Node(null,null,11);

Node node1 = new Node(null,node21,1);

Node node45 = new Node(node23,node1,45);

Node node73 = new Node(null,null,73);

Node node12 = new Node(node56,node11,12);

 

Node node34 = new Node(node45,node73,34);

Node node87 = new Node(node12,null,87);

 

Node node77 = new Node(node34,node87,77);

parent = node77;

}

 

The logic for finding height is put in getHeight() method:

private Node parent = null;

     private Stack<Node> stack = new Stack<Node>();

// the map will store the node and its current height

     private Map<Node,Integer> map = new

HashMap<Node,Integer>();    

 

private void getHeight(){

 

int highest_height =1;

int current_height = 1;

int parent_height=0;

Node temp_node = null;

stack.push(parent); // initially only the parent is present in stack

map.put(parent, current_height);

while(stack.size() != 0){

 temp_node = stack.pop();  // pop element at top from stack.

parent_height = map.get(temp_node);  // get the height

if(temp_node.getLeft() != null){  // if current node has left child

 current_height = parent_height+1; // increase the height by 1

stack.push(temp_node.getLeft()); // push the element to the stack

//put into map – put(current node, current height)

map.put(temp_node.getLeft(),current_height);   

 highest_height= (highest_height < current_height) ? current_height : highest_height;

}

 

if(temp_node.getRight() != null){  // same as left child

current_height =parent_height+1;

map.put(temp_node.getRight(),current_height);

stack.push(temp_node.getRight())     

 highest_height= (highest_height < current_height) ? current_height : highest_height;

    

}

    

System.out.println(“\n Elements currently in stack \n”);

         

for(int i =0; i<stack.size();i++){

System.out.print(” “ +((Node)stack.get(i)).getValue());  

     }

             

}

         

System.out.println(“The height is “ + highest_height);

   }

    

public static void main(String[] args) {

           BinaryTree bt = new BinaryTree();

          bt.createTree();

          bt.getHeight();

 

     }

 

}

 

The logs will show:

 

Elements currently in stack 34 87

Elements currently in stack 34 12

Elements currently in stack 34 56 11

Elements currently in stack 34 56

Elements currently in stack 34

Elements currently in stack 45 73

Elements currently in stack 45

Elements currently in stack 23 1

Elements currently in stack 23 21

Elements currently in stack 23

Elements currently in stack

The height is 5

 

 

 

• When the parent is pop from the stack a check is made to find whether it has a left child or not, if a left child is present push the left child to stack, also put the same element in a map with key as the current node and value is height which is incremented by 1 of its parent height.
• Now check if the current height is greater than the highest height or not. If it is set the highest_height to current_height.
• Similarly it works for the right child.

For given example when a check is made for parent, then 34 and 87 are push into stack.

 

Elements currently in stack 34 87 

• Now 87 is picked up and a check is made for it. Since it contains only left child as 12 , the current stack will look like

 Elements currently in stack 34 12

• The while loop iterates till the stack becomes empty.
• The main overhead in this program is to create a tree like structure by declaring the nodes explicitly.