Day22 - Binary Search Trees (Python 3)

• URL : https://www.hackerrank.com/challenges/30-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, 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.
• 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, n, denoting the number of nodes in the tree.
  • Each of the subsequent lines contains an integer, data, 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.

문제풀이

• 주어진 root값을 시작으로 왼쪽, 오른쪽으로 크고 작은 값을 넣는 이진트리에 관련된 문제였다.
• 사실 이진트리가 무엇인지 제대로 알지못해 문제는 푸는데 조금 어려움이 있었고, 구글링 결과 어느정도 개념은 잡을수 있었다.
• 다행히 hackerrank에서 주어지는 문제는 node의 height를 구하는 문제였으며, 나머지 구조들은 대부분 이미 짜여져있는 상태였다.
• 해당 문제에서 root는 height로 취급하지 않는다.
• root가 none이면 Node 클래스를 생성하여 data를 받고, 이후에 주어지는 인자들이 data보다 작으면 왼쪽으로, 크면 오른쪽으로 가는 형식으로 되어있다.
• getHeight는 왼쪽데이터와 오른쪽 데이터를 비교하여 더 큰쪽에 1씩 더해주어 height를 만들어내는 함수이다.
• 22일차가 되니 점점 알고리즘이 어려워져서 사실 잘 이해가 가지않는 부분이 있어 학습하는데 애를 먹었다.
• 이러한 알고리즘이 있다는것을 알게 되었으니, 반복 학습이 필요할듯 싶다.

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

class Node:
    def __init__(self,data):
        self.right=self.left=None
        self.data = data
class Solution:
    def insert(self,root,data):
        if root==None:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left,data)
                root.left=cur
            else:
                cur=self.insert(root.right,data)
                root.right=cur
        return root

    def getHeight(self,root):
        if root:
            leftnode = self.getHeight(root.left)
            rightnode = self.getHeight(root.right)
            
            if leftnode > rightnode:
                return leftnode + 1
            else :
                return rightnode + 1
        else:
            return -1