[Algorithm] 해커랭크 - Trees: Is This a Binary Search Tree?

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

주어진 Tree 자료구조가 BST(Binary Search Tree) 인지 판별하는 문제다.

처음에는 단순히 자료의 저장 방법에만 신경을 쓰며 풀어서 오답이 나왔다.

자료의 저장 방법은 데이터가 들어있는 노드의 값보다 작은값은 왼쪽 노드로, 큰 값은 오른쪽 노드로 진행하면서 비어있는 노드를 찾아 저장하는 방법이다.

오답이 나오고 다시 생각을 해 보니 단순히 각 노드의 Left, Right 값의 대소관계만을 고려하면 진짜로 BST인지 판별이 불가능 하다는 생각이 들었다.

BST는 특정 노드 A의 왼쪽 서브트리의 모든 값은 A의 데이터값보다 작아야 되며, 오른쪽 서브트리의 값은 A의 데이터값보다 커야 한다는 특성이 있다. 그래서 단순히 특정 노드의 좌우 자식노드의 대소관계만 판별한다고 해서 되는 것은 아니다.

또 DFS(Depth First Search)를 통해 탐색을 하게 될 경우 최솟값부터 오름차순으로 정렬되어 나오는 특징이 있다.

이진 탐색트리의 개념과 특징 --> http://makedotworld.tistory.com/admin/entry/post/?id=21&type=post&returnURL=/manage/posts/

총 3가지 방법을 적용해 풀었다. 1,2번 방법은 반절 정도만 답이 나왔고 마지막 3번째 방법만 제대로 돌아갔었다.

1. 각 노드의 좌우값의 대소 비교 

2. root 노드, 모든 자식노드를 root로 가지는 서브트리의 좌우 서브트리의 모든 값이 root의 데이터값보다 작고, 큰지 비교

3. DFS 탐색을 통해 오름차순으로 값이 나오는지 검사

1번 방법은 알고리즘 자체가 잘못됬다.

2번 방법을 통해 문제를 풀 때는 중복된 값이 나오는 경우를 고려하지 않고 풀어 답이 나오지 않았던 것 같다.

3번 방법을 이용해 풀 때 중복된 값을 조건에 넣어 코드를 제출하자 정답이 나왔다.

3번 방법을 이용한 코드는 다음과 같다.

#include<iostream>
/* 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 struct is defined as follows:
   struct Node {
      int data;
      Node* left;
      Node* right;
   }
*/
int minData = INT8_MIN;
bool checkBST(Node* root)
{
    bool isBST = true;
    if(root->left != 0)
    {
        isBST = isBST && checkBST(root->left);
    }
    if (isBST==false)
    {
        return false;
    }
    if (root->data <= minData)
    {
        return false;
    }
    else
    {
        minData = root->data;
    }
    if (root->right != 0)
    {
        isBST = isBST && checkBST(root->right);
    }
    return isBST;
}