Showing posts with label How to get height of BST using recursive way. Show all posts
Showing posts with label How to get height of BST using recursive way. Show all posts

How to get height of BST using recursive way

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
How to get height of BST using recursive way


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