Find height of binary tree in java (DFS /Recursive algorithm/example)

• Given a binary tree, find out height of binary tree using recursive algorithm.
• Traverse the binary tree using depth first search (DFS) algorithm.

What is height of binary tree?

• • Height of binary tree is number of edges from root  node to deepest leaf node.
  • We have already discussed find height of binary without recursion using BFS.

Root node is assumed to be at Height 1 and subsequently, we can calculate the height of a binary tree (refer Fig 1). The height of binary tree at each level is as follows:

Examples – calculate height of binary tree in java (recursive algorithm)

• We will discuss couple of examples to calculate height of binary tree.
• Example 1 – Calculate height of left subtree of binary tree
• Example 2 – Calculate height of right subtree of binary tree
• We will consolidate the height of left & right subtree, to get height of binary tree.
• Height of binary tree = max (height of left subtree, height of right subtree).

Example 1: find height of left sub-tree, rooted at node A.

1. Go to node B
   • Find the height of left subtree
     • Height of left subtree = 1
   • Find the height of right subtree
     • Height of right subtree = 1
2. Height of a binary binary tree will be
   • Height = max(height of left subtree, height of right subtree) + 1 ( Node B).
   • Height = max(1,1) + 1 = 2

Example 2: find height of right sub-tree, rooted at node A.

1. Go to node C
   • Find the height of left subtree
     • Go to Node F and apply Example 1 algorithm.
     • At Node F, Height of binary Tree = 2
   • Find the height of right subtree
     • Height of right subtree = 1
2. Height of a binary binary tree will be
   • Height = max(height of left subtree, height of right subtree) + 1 ( Node C).
   • Height = max(2,1) + 1 = 3

Algorithm: height of binary tree in java using recursive algorithm

• Calculate height of left subtree (example1)
  • Height at Node B is 2
• Calculate height of right subtree (example2)
  • Height at Node C is 3
• Height of binary tree (at node A) = max (height of left sub tree, height of right subtree).
• Height of binary tree (at node A) = max (2,3) + 1 (height of node A)
• Height of binary tree (at node A) = 4

The time complexity of algorithm is O(n) .

Program – calculate height of binary tree in java (Depth first search)

1.) HeightOfTree Class: 

• HeightOfTree class is used to find the height of binary tree using depth first search algorithm.

package org.learn.Question;

public class HeightOfTree {
 
 public static int heightOfTree(Node root) {
  if (null == root)
   return 0;
  int hLeftSub = heightOfTree(root.left);
  int hRightSub = heightOfTree(root.right);
  return Math.max(hLeftSub, hRightSub) + 1;
 }
}

2.) Node:

• Node class representing the nodes in a binary tree.

package org.learn.Question;

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

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }

 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

• We are the creating binary tree in main method.
• We are calling method of HeightOfTree class, to calculate the height of a binary tree.

package org.learn.Client;

import org.learn.Question.HeightOfTree;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(70);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(90);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(75);
  Node F = Node.createNode(35);
  Node G = Node.createNode(55);
  // Level 3
  Node H = Node.createNode(10);
  Node I = Node.createNode(30);

  // connect Level 0 and 1
  A.left  = B;
  A.right = C;
  // connect level 1 and level 2
  B.left  = D;
  B.right = E;
  C.left  = F;
  C.right = G;
  // connect level 2 and level 3
  F.left  = H;
  F.right = I;

  int height = HeightOfTree.heightOfTree(A);
  if (height > 0) {
   System.out.println("Height of a Binary Tree is : " + height);
  }
 }
}

Output – height of a binary tree (depth first search algorithm):

Height of a Binary Tree is : 4

Download Code – Height Of binary tree recursive algorithm