- 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:
S. No. | Nodes | Height |
---|---|---|
1 | A | 1 |
2 | B,C | 2 |
3 | D,E,F,G | 3 |
4 | H,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.
- 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
- Find the height of left subtree
- 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.
- 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
- Find the height of left subtree
- 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: 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
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