[C 자료구조] Tree - Is This a Binary Search Tree?

0) 제목

• Hackerrank 의 Tree 부분의 Is This a Binary Search Tree? 문제입니다.

• C언어를 이용하여 풀었습니다.

1) 문제설명

• 이진트리(Binary Tree)의 root 노드의 포인터가 파라미터로 주어집니다.

• 주어진 트리가 이진트리(Binary Tree) 인지 이진탐색트리(Binary Search Tree) 인지 검사하는 문제입니다.

• 만약 이진탐색트리라면 true를 아니라면 false를 리턴하는 문제입니다.

2) 풀이과정

• 처음에는 단순하게 이진트리 이므로, 

• 재귀함수를 이용하여 각 노드마다 이진탐색 트리의 조건을 만족하는지 체크하면서 

• 함수를 호출하는 방식을 시도했었습니다.

• 그러다가 이진 탐색 트리의 특성을 곰곰히 생각하면서, 다른식으로 접근해보려고 시도했습니다.

• 이진 탐색트리의 특성은 "왼쪽 자식 노드의 키 값 < 부모 노드의 키값 < 오른쪽 자식 노드의 키값" 이라는 것 입니다.

• 이것을 조금만 더 생각해 보면, 트리의 순회 중에서 중위 순회(Inorder Traversal)로 순회를 하게 된다면,

• 작은 키값부터 큰 키값 순으로 정렬이 되겠고, 비교가 가능할 것이라고 판단하였습니다.

• 중위순회를 통해서  배열에 각 키값을 정렬하고, 오름차순인지 검사하는 방식으로 코드를 작성했습니다.

3) 코드

/* 
   typedef struct _Node {
      int data;
      struct _Node * left;
      struct _Node * right;
   } Node;
*/
 
int arr[1024];
int n=0;
 
void inorderTraversal(Node * pd){
    if(pd == NULL) return ;
 
    inorderTraversal(pd->left);
    arr[n++] = pd->data;
    inorderTraversal(pd->right);
}
 
//bool 부분만 C++ 문법 사용 : 문제에서 C++ 데이터 타입인 bool을 주었습니다. 
bool checkBST(Node* root) {
 
    inorderTraversal(root);
 
    for(int i=0; i<n-1; i++){
        if(arr[i] >= arr[i+1]) return false;
    }
    
    return true;
}

4) 인증

주석 내부에 있는 부분은 C언어 문법에 맞게 고쳤습니다.

(Hackerrank 에서는 C++ 문법으로 지원)

경로 : Dashboard>Data Structures>Trees>Is This a Binary Search Tree?

출처 : [HackerRank] https://www.hackerrank.com/challenges/is-binary-search-tree/