[HackerRank] Is This a Binary Search Tree? (Java, 이진탐색트리 판단, 확인)

www.hackerrank.com/challenges/is-binary-search-tree/problem

Is This a Binary Search Tree? | HackerRank

 

 

## 접근방법

---

정말 좋은 문제다, 지금까지 이진탐색트리의 시간복잡도, 삽입, 탐색에 관해서만 생각했었다.

 

 

 

만들어진 이진트리를 판단하는 문제는 접해보지 않았다. 어떻게 이진트리임을 판단할 것인가?

 

 

 

처음에는 단순 자식으로만 값의 비교를 통해서 확인하려고 했다. 이것은 아주 위험하고 어리석은 생각이다. 이진트리는 왼쪽 이진트리의 노드들은 모두 현재 값보다 작아야 하고, 오른쪽 이진트리의 노드들은 모두 현재 값보다 커야 한다. 

 

 

 

이진 트리들의 노드들을 경유하다 보면, 값의 범위가 결정되게 된다. 루트 노드만 생각해도, 왼쪽 이진트리로 이동하면 범위의 최댓값은 루트 노드보다 작아야 한다. 오른쪽 이동트리로 이동하면 범위의 최솟값은 루트 노트보다 커야 한다. 

 

 

 

위의 방식으로, 노드들은 경유할 때마다 특정 범위로 점차 줄어든다. 특정 범위에 해당되지 못한다면, 이진탐색트리가 될수 없다. 이 점을 착안해서 코드를 작성하면 된다.

 

 

## 해설코드 

---

 

/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.  
 
The Node class is defined as follows:
    class Node {
    int data;
    Node left;
    Node right;
     }
*/
    boolean checkBST(Node root) {
        return check(root, 0, 10000);
    }
 
    boolean check(Node root, int min, int max){
        if(root.data <= min || root.data >= max)
            return false;
        
        boolean ret = true;
        if(root.left != null){
            ret = ret && check(root.left, min,  root.data);
        }
        
        if(root.right != null){
            ret = ret && check(root.right, root.data, max);    
        }
        
        return ret;
    }