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. public static int getHeight(Node root) {
  13. return root == null ? -1 : 1 + Math.max(getHeight(root.left), getHeight(root.right));
  14. }
  15. public static Node insert(Node root,int data){
  16. if(root==null){
  17. return new Node(data);
  18. }
  19. else{
  20. Node cur;
  21. if(data<=root.data){
  22. cur=insert(root.left,data);
  23. root.left=cur;
  24. }
  25. else{
  26. cur=insert(root.right,data);
  27. root.right=cur;
  28. }
  29. return root;
  30. }
  31. }
  32. public static void main(String args[]){
  33. Scanner sc=new Scanner(System.in);
  34. int T=sc.nextInt();
  35. Node root=null;
  36. while(T-->0){
  37. int data=sc.nextInt();
  38. root=insert(root,data);
  39. }
  40. int height=getHeight(root);
  41. System.out.println(height);
  42. }
  43. }