[2019.01.11] Binary Search Trees

Problem

Objective 
Today, we're working with Binary Search Trees (BSTs). Check out the Tutorial tab for learning materials and an instructional video!

Task 
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, , 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.

Input Format

The locked stub code in your editor reads the following inputs and assembles them into a binary search tree: 
The first line contains an integer, , denoting the number of nodes in the tree. 
Each of the  subsequent lines contains an integer, , denoting the value of an element that must be added to the BST.

Output Format

The locked stub code in your editor will print the integer returned by your getHeight function denoting the height of the BST.

Sample Input

7
3
5
2
1
4
6
7

Sample Output

3

Explanation

The input forms the following BST:

The longest root-to-leaf path is shown below:

There are  nodes in this path that are connected by  edges, meaning our BST's . Thus, we print  as our answer.

How I solved the problem

# Binary search Tree 에 대해서 알기

# 정보를 찾아가는 방식 중 하나

# 가운데를 기점으로 왼쪽과 오른쪽에 가운데의 작은 수와 큰 수를 배치하여 트리 형태로 도식화 할 수 있음..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

import java.util.*; import java.io.*; class Node{     Node left,right;     int data;     Node(int data){         this.data=data;         left=right=null;     } } class Solution{     public static int getHeight(Node root){ //가장 아래 레벨이 몇 단계인지 구함       //Write your code here       int rightHeight = 0;       int leftHeight = 0;       if (root.left != null) {           leftHeight = getHeight(root.left) + 1;       }       if (root.right != null) {           rightHeight = getHeight(root.right) + 1;       }       int result = (rightHeight > leftHeight? rightHeight : leftHeight);       return result;     }     public static Node insert(Node root,int data){ //binary search tree로 만드는 부분         if(root==null){             return new Node(data);         }         else{             Node cur;             if(data<=root.data){                 cur=insert(root.left,data);                 root.left=cur;             }             else{                 cur=insert(root.right,data);                 root.right=cur;             }             return root;         }     }      public static void main(String args[]){         Scanner sc=new Scanner(System.in);         int T=sc.nextInt();         Node root=null;         while(T-->0){             int data=sc.nextInt();             root=insert(root,data);         }         int height=getHeight(root);         System.out.println(height);     } } Colored by Color Scripter

cs

[출처 : https://www.hackerrank.com ]