How to get height of BST using recursive way

How to get height of BST using recursive way

Interview Questions  

The height of a Binary Search Tree is the length of the longest downward path to a leaf from root node. This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
In below example the height of the tree is 5, i.e., from root(10) which goes to 3 -> 5 -> 7 -> 8 -> 9. So maximum height of the tree is 5

Lets see simple Java code to get the height of a BST tree using recursion.

class Node {
 Node left, right;
 int data;

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

public class TreeHeight {

 public static void main(String[] args) {

  int a[] = { 1, 2, 3, 4, -1, -2, -3, -4, -5 };
  //int a[] = { 10,3,15,2,5,19,7,8,9,20,1 };
  
  Node root = null;
  TreeHeight tree = new TreeHeight();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }

  int height = tree.getBSTHeight(root);
  System.out.println("Binary Tree maximum height : " + height);
 }


 public int getBSTHeight(Node node) {
  if (node != null)
   return Math.max(getBSTHeight(node.left), 

                                        getBSTHeight(node.right)) + 1;
  else
   return -1;
 }
 
 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

Binary Tree maximum height : 5