Contents

Tree: Height of a Binary Tree

Binary tree의 높이를 구하는 문제이다. Tree를 class수준에서 높이를 구하는 것이 아니라 root node에 대해서만 input으로 받는다는 것이 특징이다.

Problem

https://s3.amazonaws.com/hr-assets/0/1527626183-88c8070977-isitBSTSample0.png
HackerRank: Binary Tree

The height of a binary tree is the number of edges between the tree’s root and its furthest leaf. For example, the following binary tree is of height 2.

Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s):

  • root: a reference to the root of a binary tree.

문제가 요구하는 바는 간단하다. height함수에 root Node가 주어졌을 때, tree의 높이를 구하는 것이다. NodeBinarySearchTree 클래스는 다음과 같이 정의된다.

 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
class Node:
    def __init__(self, info): 
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 

class BinarySearchTree:
    def __init__(self): 
        self.root = None

    def create(self, val):  
        if self.root == None:
            self.root = Node(val)
        else:
            current = self.root
         
            while True:
                if val < current.info:
                    if current.left:
                        current = current.left
                    else:
                        current.left = Node(val)
                        break
                elif val > current.info:
                    if current.right:
                        current = current.right
                    else:
                        current.right = Node(val)
                        break
                else:
                    break

Answer

1
2
3
4
5
def height(root):
    if root is None:
        return -1
    
    return max(height(root.left) + 1, height(root.right) + 1)

Explanation

이 문제처럼 같은 방식을 단계별로 반복한다면 recursive한 함수사용을 고민해보아야 한다. 또한 recursive하게 하는 대상에 대해서는 함수 내에서 모두 해당 함수표현으로 나타내어야 한다. height을 recursive하게 표현하므로 함수 내부에서도 높이를 표현할 때 height을 사용해 표현하면 된다. Recursive 함수를 만들 때 가장 중요한 것 중 하나는 함수가 끝나는 조건을 잘 설계해야 한다는 것이다. Tree의 높이를 셀 때 root는 0으로 세므로 root에서는 -1을 반환하면 된다.

Reference