Monday, 5 March 2018

Program to find the height of Binary Search Tree(BST) in Java

           In previous post, discussed about to max and min value of BST. In this post, we will see how to find the height of binary search tree.

          Height of binary tree is number of edges from root  node to deepest leaf node. Height of empty tree is 0.

See the below BST,  Height of BST is 4.
Height of Binary Search Tree
Height of Binary Search Tree

BSTHeightCalc.java, Using recursion

package com.practice;

class Node {
 
      int data;
      Node leftChild;
      Node rightChild;
 
      public Node(int data) {
           this.data = data;
           leftChild = null;
           rightChild = null;
      }
}

public class BSTHeightCalc {
 
      Node root;
 
      int calcBSTHeight() {
            return calcBSTHeight(root);
      }
 
      int calcBSTHeight(Node node) {
            if (node == null) {
                  return 0;
            }
  
            return Math.max(calcBSTHeight(node.leftChild), calcBSTHeight(node.rightChild))+1;
      }
 
      public static void main(String[] args) {
              BSTHeightCalc height = new BSTHeightCalc();
              height.root = new Node(18);
              height.root.leftChild = new Node(12);
              height.root.rightChild = new Node(28);
              height.root.leftChild.rightChild = new Node(32);
              System.out.println("Height of the BST:-"+height.calcBSTHeight());
      }
}

Output :--  Height of the BST:-3



Related post:--
1)  Program to find maximum and minimum value from Binary Search Tree in Java
2) Java Program to delete a node from Binary Search Tree(BST)
3) Java Program to Count the number of nodes and leaf nodes of Binary Tree
4) Java Program to Reverse a Linked List using Recursion and Loops

No comments:

Post a comment