Find the height of binary tree.

Given a binary tree, find its height.
Algorithm

Height of the binary tree can be easily calculated using recursion.

Height of tree= Maximum (Height of left subtree +Height of right subtree)  + 1 ( For the node itself ).

Now the left and right subtree height can be calculated with the help of recursion.

Example

Height of binary tree is the number of edges between’s tree root and its farthest leaf. A tree containing a single node has height 0.

Consider the tree:

For this tree, height is 3. It is obtained with the help of recursion. Each subtree gives its height  and at last we get the height  of  the complete tree. It is explained as:

  1. height(50) is called initially. It calls height(25) and height(75)
  2. height(25) calls height(12) and height(37)
  3. height(12) returns 0 and height(37) calls height(30) (returns 0) and height(40) (returns 0). So height(37) returns max (0,0) + 1 i.e 1
  4. Now height(25) returns max(0,1) + 1 i.e.2. This is height of left subtree of 50
  5. In the similar way, we get height of right subtree of 50. The max would be 2.
  6. Now height of the tree would be-  max ( left subtree height i.e. 2 , right subtree height i.e. 2 ) + 1(for the node itself) = 3
  7. Hence height of the tree is 3.

It is explained as follows:

 

 

Code

[code language=”css”]

import java.util.*;

public class test {

// Binary tree class
public static class BinaryTree {
// Node class
public class Node {

int data;
Node left;
Node right;

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

}

private Node root;

public BinaryTree(int[] pre, int[] post) {
this.root = this.construct(pre, 0, pre.length – 1, post, 0, post.length – 1);

}

private Node construct(int[] pre, int presi, int preei, int[] post, int postsi, int postei) {

// this case occurs when a node has only one child
if (presi > preei) {
return null;
}

Node node = new Node(pre[presi]);
node.left = null;
node.right = null;

if (presi == preei) {
return node;
}

//Searching pre[presi + 1] in postorder array
int pos = -1;
for (int i = postsi; i <= postei; i++) {
if (post[i] == pre[presi + 1]) {
pos = i;
break;
}
}

//Number of elements in left subtree
int clc = pos – postsi + 1;

//Left subtree
node.left = this.construct(pre, presi + 1, presi + clc, post, postsi, pos);

//Right subtree
node.right = this.construct(pre, presi + clc + 1, preei, post, pos + 1, postei – 1);

return node;

}

public int height() {
return this.height(this.root);
}

//Function to find height of binary tree
private int height(Node node) {

//Base case
if (node == null) {
return -1;
}

//Calculate height of left subtree
int lht = this.height(node.left);

//Calculate height of right subtree
int rht = this.height(node.right);

//Height of the tree is max of left and right subtree height + 1 (for the node itself)
int rv = Math.max(lht, rht) + 1;
return rv;
}
}

public static void main(String[] args) throws Exception {

// Construct binary tree

int[] pre = { 50, 25, 12, 37, 30, 40, 75, 62, 60, 70, 87 };
int[] post = { 12, 30, 40, 37, 25, 60, 70, 62, 87, 75, 50 };

BinaryTree bt = new BinaryTree(pre, post);
System.out.println(bt.height());

}

}

[/code]

Time Complexity

As we are traversing each node of tree exactly once, so the time complexity is O(n).

 

Please Login/Signup to comment