Find height of binary tree in Java - Recursive and Iterative

Topics covered

1. Find height of binary tree - Recursive
2. Find height of binary tree - Iterative
3. Complete sample program- recursive and iterative

Height(depth) of binary tree is length of longest path form root to leaf in the given binary tree.For the following binary tree height is 5. In this post we have discussed both recursive and iterative approach to find size of binary tree. 

Sample code for finding height of binary tree in Java - recursive approach
Algorithm:-
1. Traverse given binary tree and recursively calculate height of left and right subtree of given node, increment 1 and assign it to given node.
3. Repeat step 1 for each node and bubble up calculated height up to root.

/* Recursive approach to find height of binary tree */
public int findHeightOfBinaryTreeRecursive(Node root) {
 if (root == null) {
  return 0;
 }
 /*
  * Call function recursively for left and right child and find height of
  * left and right child
  */
 int lh = findHeightOfBinaryTreeRecursive(root.leftChild);
 int rh = findHeightOfBinaryTreeRecursive(root.rightChild);
 /* Check for length of left and right subtree height */
 if (rh > lh) {
  return 1 + rh;
 } else {
  return 1 + lh;
 }
}

Sample code for finding height of binary tree in Java - iterative approach
Algorithm:-
1. Traverse given binary tree in level order and at end of each level insert special Node to identify all nodes of that level has been covered.
2. Insert root into queue and special node too.
3. Loop until queue is not empty, remove an element and check for removed element is special node or not - If special node is found, increment heigh and insert special node as marker node for next level.
Note:- Before adding special node, do check for empty queue. If queue is empty means, we have covered all nodes of the tree so no need to insert special node.

/* Iterative approach to find height of tree-level order traversal */
public int findHeightOfBinaryTreeIterative(Node root) {
 Node temp;
 int height = 0;
 Queue<Node> queue = new ArrayDeque<>();
 queue.add(root);
 Node dummy = new Node(Integer.MIN_VALUE);
 queue.add(dummy);
 while (!queue.isEmpty()) {
  temp = queue.remove();
  if (temp.data == Integer.MIN_VALUE) {
   height++; // Increment height
   /* Insert special node queue if queue is not empty
    * since all nodes of that level has been covered*/
   if (!queue.isEmpty())
    queue.add(dummy);
  }
  Node lc = temp.leftChild;
  Node rc = temp.rightChild;
  if (lc != null) {
   queue.add(lc);
  }
  if (rc != null) {
   queue.add(rc);
  }

 }
 return height;
}

Complete sample program -finding height of binary tree in Java (Iterative and Recursive)

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.Queue;

public class HeightOfBinaryTree {

/* Iterative approach to find height of tree-level order traversal */
public int findHeightOfBinaryTreeIterative(Node root) {
 Node temp;
 int height = 0;
 Queue<Node> queue = new ArrayDeque<>();
 queue.add(root);
 Node dummy = new Node(Integer.MIN_VALUE);
 queue.add(dummy);
 while (!queue.isEmpty()) {
  temp = queue.remove();
  if (temp.data == Integer.MIN_VALUE) {
   height++; // Increment height
   /* Insert special node queue if queue is not empty
    * since all nodes of that level has been covered*/
   if (!queue.isEmpty())
    queue.add(dummy);
  }
  Node lc = temp.leftChild;
  Node rc = temp.rightChild;
  if (lc != null) {
   queue.add(lc);
  }
  if (rc != null) {
   queue.add(rc);
  }

 }
 return height;
}

/* Recursive approach to find height of binary tree */
public int findHeightOfBinaryTreeRecursive(Node root) {
 if (root == null) {
  return 0;
 }
 /*
  * Call function recursively for left and right child and find height of
  * left and right child
  */
 int lh = findHeightOfBinaryTreeRecursive(root.leftChild);
 int rh = findHeightOfBinaryTreeRecursive(root.rightChild);
 /* Check for length of left and right subtree height */
 if (rh > lh) {
  return 1 + rh;
 } else {
  return 1 + lh;
 }
}

 public static void main(String[] args) {
  HeightOfBinaryTree heObj = new HeightOfBinaryTree();
  Node root = heObj.new BinaryTree().createTree();
  int size = heObj.findHeightOfBinaryTreeIterative(root);
  System.out.println("Iterative-  size of binary tree :- " + size);

  size = heObj.findHeightOfBinaryTreeRecursive(root);
  System.out.println("Recursive- size of binary tree :-  " + size);

 }

 class Node {
  private int data;
  private Node leftChild;
  private Node rightChild;

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

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setRightChild(new Node(27));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getLeftChild().getLeftChild().getRightChild()
     .setLeftChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   root.getRightChild().getLeftChild().setLeftChild(new Node(32));
   return root;
  }
 }

}

=======Sample output=====
 Iterative- size of binary tree :- 5
Recursive- size of binary tree :- 5
=======================