Finding Height of a node in a Binary Tree

This article explains how to find the height of a node in a given binary tree. Finding height of a node is an important factor while building self balancing tree or AVL tree. The height of a node plays an important role in tree rotation while building AVL trees. As we know, height of an empty tree (with no nodes) is -1 and height of a tree with only one node (root node) is 0. We apply same concept while calculating the height of a given node in a tree. To illustrate the concept we build binary search tree as below:

Binary Search Tree

Please note that above tree is not balanced.

We need to find the height of node 25. So we start from root node of the tree which is 5. We prefer visiting left subtree first and then right subtree. After visiting each subtree on left and right side we check if current node has same data as that of node for which we need to find the height. To find out the height of a node we write concise code with recursion. Below is the code to find out height of a given node.

public class HeightBSTNode {
  Node root;
  Node add (Node node, int data) {
     if (null == node) return new Node (data);
     else if (data < node.data) node.left = add (node.left, data);
     else if (data > node.data) node.right = add (node.right, data);
     return node;
  }
  static int findHeight (Node Node, int data, int height, Value V) {
     if (Node == null) return height;
     // Go to left subtree
     int level = findHeight (Node.left, data, height+1, V);
     if (Node.data == data) V.v = level;
     
     // Go to right subtree
     level = findHeight (Node.right, data, height+1, V);
     if (Node.data == data) V.v = level;
     return height;
  }
  public static void main (String[] args) {
     HeightBSTNode a = new HeightBSTNode();
     Value V = new Value();
     
     // create a tree.
     a.root = add (a.root, 5);
     a.root = add (a.root, 3);
     a.root = add (a.root, 2);
     a.root = add (a.root, 10);
     a.root = add (a.root, 15);
     a.root = add (a.root, 12);
     a.root = add (a.root, 25);
     a.root = add (a.root, 35);
    findHeight (a.root, 25, -1, V);
    System.out.println ("Height of node "+25+" is "+V.v);
  }
}
class Node {
  int data;
  Node left, right;  
  
  Node (int data) {
    this.data=data;
  }
}
class Value {
  int v;
}

The main() starts calling findHeight() with root, data, -1, V. In our case, the data for which we need to find the height is node with value 25, initial height we assume as -1 and V is used to store height of the node which we can refer when call returns to main(). The level is used to store the height of left subtree and right subtree. When each recursive call is made we increment height by 1. When both left subtree and right subtree call returns, we return the height on the call stack. This is important when we reach from left sub tree to root and right subtree to root. The time complexity of findHeight() is O(N).

After running the program it prints:

Height of node 25 is 3
Similarly the height of nodes 35 and 2 is as below
Height of node 35 is 4
Height of node 2 is 2

Conclusion

In this article, we visited the code to calculate the height of a given node in a binary tree. Calculating the height of a node is an important step in tree rotation algorithm.