Find height of binary tree in java using recursive algorithm (example)

By | November 26, 2015
  • 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.
level binary tree

Fig 1: Height of binary tree

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:

S. No.Nodes  Height
1A 1
2B,C 2
3D,E,F,G 3
4H,I 4

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
height left subtree

Fig 2: Height of binary tree

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
height right subtree

Fig 3: Height of binary tree is 3

Algorithm: find 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
height left right subtree

Fig 4: Height of binary tree

The time complexity of algorithm is O(n) .

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

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 using depth first search algorithm:


Height of a Binary Tree is : 4

Download Code – find Height Of binary tree recursive algorithm