기술면접 - 이진 검색 트리 유효성 검사 (Validate Binary Search Tree)

 

중위 순회(Inorder Traversal)와 범위 검사(Range Check)를 활용한 C 언어 구현

이진 검색 트리(BST)란?

이진 검색 트리(BST)는 각 노드의 왼쪽 서브트리 값이 현재 노드보다 작고, 오른쪽 서브트리 값이 현재 노드보다 큰 규칙을 따르는 트리입니다. BST는 다음과 같은 성질을 만족합니다:

• 왼쪽 서브트리: 현재 노드보다 작은 값만 포함.
• 오른쪽 서브트리: 현재 노드보다 큰 값만 포함.
• 재귀적 성질: 모든 서브트리도 BST여야 함.

이 규칙을 위반하면 유효한 BST가 아니므로, 이를 확인하는 알고리즘이 필요합니다. 이번 포스트에서는 중위 순회와 범위 검사 두 가지 방법을 C 언어로 구현해 봅니다.

1. 중위 순회(Inorder Traversal) 방법

개념

BST의 중위 순회는 노드를 오름차순으로 방문합니다. 즉, 중위 순회 중 이전 노드의 값보다 현재 노드의 값이 작거나 같으면 BST 규칙을 위반한 것입니다.

장점

• 구현이 간단하고 직관적.
• 추가 메모리 사용이 최소화됨.

단점

• 재귀 호출로 인해 트리의 높이에 비례하는 스택 공간 필요.

C 언어 구현

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 트리 노드 구조체 정의
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 이전 노드 값을 저장하는 전역 변수
int prev = INT_MIN;

// 중위 순회로 BST 유효성 검사
int isValidBST_inorder(TreeNode* root) {
    if (root == NULL) {
        return 1; // 빈 트리는 유효
    }

    // 왼쪽 서브트리 검사
    if (!isValidBST_inorder(root->left)) {
        return 0;
    }

    // 현재 노드 값이 이전 값보다 작거나 같으면 BST 아님
    if (root->val <= prev) {
        return 0;
    }
    prev = root->val; // 이전 값 업데이트

    // 오른쪽 서브트리 검사
    return isValidBST_inorder(root->right);
}

// 테스트용 메인 함수
int main() {
    // 트리 예시: 유효한 BST
    //     2
    //    / \
    //   1   3
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 2;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 1;
    root->right->val = 3;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right->left = NULL;
    root->right->right = NULL;

    prev = INT_MIN; // prev 초기화
    if (isValidBST_inorder(root)) {
        printf("유효한 BST입니다.\n");
    } else {
        printf("유효하지 않은 BST입니다.\n");
    }

    // 메모리 해제 (생략)
    return 0;
}

코드 설명

• TreeNode 구조체: 트리 노드를 정의하며, 값(val)과 왼쪽/오른쪽 자식 포인터를 가짐.
• prev 변수: 중위 순회 중 이전 노드 값을 저장. 초기값은 INT_MIN.
• isValidBST_inorder 함수:
  • 빈 트리면 1 반환.
  • 왼쪽 서브트리 재귀 호출.
  • 현재 노드 값이 prev보다 작거나 같으면 0 반환.
  • prev를 현재 값으로 업데이트 후 오른쪽 서브트리 검사.
• 메인 함수: 간단한 BST를 만들어 테스트.

2. 범위 검사(Range Check) 방법

개념

각 노드에 허용되는 값의 범위(min, max)를 설정하고, 노드 값이 이 범위 내에 있는지 확인합니다. 루트는 전체 범위를 가지며, 자식 노드로 갈수록 범위가 좁아집니다.

장점

• 한 번의 방문으로 검사 가능.
• BST 성질을 명확히 반영.

단점

• 범위 관리가 약간 복잡.

C 언어 구현

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 트리 노드 구조체 정의
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 범위 검사로 BST 유효성 확인
int isValidBST_range(TreeNode* root, long min, long max) {
    if (root == NULL) {
        return 1; // 빈 트리는 유효
    }

    // 현재 노드 값이 범위를 벗어나면 BST 아님
    if (root->val <= min || root->val >= max) {
        return 0;
    }

    // 왼쪽 서브트리: 최대값은 현재 노드 값
    if (!isValidBST_range(root->left, min, root->val)) {
        return 0;
    }

    // 오른쪽 서브트리: 최소값은 현재 노드 값
    if (!isValidBST_range(root->right, root->val, max)) {
        return 0;
    }

    return 1;
}

// 초기 호출용 함수
int isValidBST(TreeNode* root) {
    return isValidBST_range(root, LONG_MIN, LONG_MAX);
}

// 테스트용 메인 함수
int main() {
    // 트리 예시: 유효하지 않은 BST
    //     5
    //    / \
    //   1   4
    //      / \
    //     3   6
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 5;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 1;
    root->right->val = 4;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 3;
    root->right->right->val = 6;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    if (isValidBST(root)) {
        printf("유효한 BST입니다.\n");
    } else {
        printf("유효하지 않은 BST입니다.\n");
    }

    // 메모리 해제 (생략)
    return 0;
}

코드 설명

• isValidBST_range 함수:
  • 빈 트리면 1 반환.
  • 노드 값이 min과 max 범위를 벗어나면 0 반환.
  • 왼쪽 서브트리는 max를 현재 값으로, 오른쪽 서브트리는 min을 현재 값으로 설정해 재귀 호출.
• isValidBST 함수: 초기 범위를 LONG_MIN과 LONG_MAX로 설정.
• 메인 함수: 유효하지 않은 BST(4가 5의 오른쪽에 있지만 3은 5보다 작음)를 테스트.

두 방법 비교

기준	중위 순회	범위 검사
복잡도	O(n)	O(n)
추가 공간	O(h) (h는 트리 높이)	O(h) (재귀 스택)
구현 난이도	쉬움	약간 복잡
직관성	BST 성질 활용	범위로 명확히 확인

결론

중위 순회와 범위 검사 모두 BST 유효성을 확인하는 데 효과적입니다. 중위 순회는 간단하고 BST의 오름차순 성질을 잘 활용하며, 범위 검사는 각 노드의 값이 규칙을 따르는지 명확히 확인합니다. 상황에 따라 적합한 방법을 선택하면 됩니다.

위 코드는 테스트 예시를 포함해 실제로 동작하는 형태로 제공되었으니, 여러분의 프로젝트나 학습에 활용해 보세요! 구글 블로그에 이 내용을 업로드하여 많은 사람들과 공유할 수 있습니다.