Java Day 22: Binary Search Trees

The height of a binary search tree is the number of edges between the tree's root and its furthest leaf. You are given a pointer, root, pointing to the root of a binary search tree. Complete the getHeight function provided in your editor so that it returns the height of the binary search tree.



  1. import java.util.*;

  2. import java.io.*;

  3. class Node{

  4.     Node left,right;

  5.     int data;

  6.     Node(int data){

  7.         this.data=data;

  8.         left=right=null;

  9.     }

  10. }

  11. class Solution{

  12. 

  13. 	public static int getHeight(Node root) {

  14.         return root == null ? -1 : 1 + Math.max(getHeight(root.left), getHeight(root.right));

  15.     }

  16. 

  17. 	public static Node insert(Node root,int data){

  18.         if(root==null){

  19.             return new Node(data);

  20.         }

  21.         else{

  22.             Node cur;

  23.             if(data<=root.data){

  24.                 cur=insert(root.left,data);

  25.                 root.left=cur;

  26.             }

  27.             else{

  28.                 cur=insert(root.right,data);

  29.                 root.right=cur;

  30.             }

  31.             return root;

  32.         }

  33.     }

  34.     public static void main(String args[]){

  35.             Scanner sc=new Scanner(System.in);

  36.             int T=sc.nextInt();

  37.             Node root=null;

  38.             while(T-->0){

  39.                 int data=sc.nextInt();

  40.                 root=insert(root,data);

  41.             }

  42.             int height=getHeight(root);

  43.             System.out.println(height);

  44.         }	

  45. }
download android app