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