Hackerrank - Binary Search Trees

오늘 풀어본 문제는 Hackerrank의 Binary Search Tree 입니다.

기본 Tree의 구조 생성 및 Node의 정의는 코드로 짜져 있고, Tree의 Height을 구하는 문제였습니다.

 

https://www.hackerrank.com/challenges/30-binary-search-trees/problem

불러오는 중입니다...

Binary Search Tree란 다음과 같은 구조를 갖는 트리를 말합니다.

 

Binary Search Tree의 기본 구조

1. 특정 노드의 왼쪽 subtree는 특정 노드보다 작은 값을 갖는다.

2. 특정 노드의 오른쪽 subtree는 특정 노드보다 큰 값을 갖는다.

3. 모든 노드들은 Binary Search Tree이다.

 

즉 아래와 같은 그림에서는, Height 가 2가 됩니다. (※ Height를 2로 보는지 3으로 보는지는 사람마다 다른 것 같습니다. 문제에서는 Root Node를 Height에 포함시키지 않습니다. ※)

[Height가 2인 Binary Tree]

이 문제는 대충 감이 오는 것처럼, Recursive 구조를 활용합니다.

 

1) 특정 노드가 Null인 경우 -1을 반환합니다.(마지막에 다다랐을 때)

2) Left Subtree의 Height와 Right Subtree의 Height을 Recursive를 활용하여 구합니다.

3) Left Subtree의 Height와 Right Subtree의 Height를 비교하여, (더 큰 것 + 1)을 반환합니다.

 

이렇게 구하면 마지막에 Root Node를 구하게 되고, 초기 값 -1을 준 덕분에 이 문제에서 말하는 Height를 구할 수 있습니다.

 

이상 끝-!