C++로 확인하는 배열이 이진 탐색 트리(BST)의 전위 순회가 될 수 있는지 검사하기

배열에 저장된 요소들이 어떤 이진 탐색 트리(Binary Search Tree, BST)의 전위 순회(preorder traversal) 결과가 될 수 있는지 판별하는 문제를 살펴보겠습니다.

예를 들어 수열이 {40, 30, 35, 80, 100}이라면, 이 수열은 다음과 같은 이진 탐색 트리를 구성할 수 있습니다.

접근 방법: 스택 활용

이 문제는 스택(stack) 하나만으로 O(n) 시간 안에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

빈 스택을 정의하고, 현재 루트(root) 값을 음의 무한대(INT_MIN)로 초기화합니다.
전위 순회 수열의 각 요소에 대해 다음 과정을 반복합니다.
- 현재 요소가 루트 값보다 작다면, BST의 성질(오른쪽 서브트리에는 루트보다 큰 값만 존재)을 위반하므로 false를 반환합니다.
- 현재 요소가 스택의 최상단(top) 값보다 클 동안 스택에서 요소를 계속 꺼내고, 마지막으로 꺼낸 요소를 새로운 루트로 설정합니다. 이는 왼쪽 서브트리 순회가 끝나고 오른쪽 서브트리로 넘어갔음을 의미합니다.
- 현재 요소를 스택에 push합니다.
모든 요소를 처리한 후에도 위반이 없다면 true를 반환합니다.

C++ 구현 예제

#include <iostream>
#include <stack>
using namespace std;

bool isValidPreorder(int pre[], int n) {
    stack<int> stk;
    int root = INT_MIN; // 루트를 음의 무한대로 초기화
    for (int i = 0; i < n; i++) {
        // 루트보다 작은 값이 나오면 BST 성질 위반
        if (pre[i] < root)
            return false;
        // 현재 값보다 작은 요소들을 모두 pop하며 루트 갱신
        while (!stk.empty() && stk.top() < pre[i]) {
            root = stk.top();
            stk.pop();
        }
        stk.push(pre[i]);
    }
    return true;
}

int main() {
    int pre[] = {40, 30, 35, 80, 100};
    int n = sizeof(pre) / sizeof(pre[0]);
    if (isValidPreorder(pre, n))
        cout << "This can form BST";
    else
        cout << "This can not form BST";
}

실행 결과

This can form BST

동작 원리 정리

위 코드에서 {40, 30, 35, 80, 100}이 통과되는 과정을 단계별로 보면 다음과 같습니다.

40: 루트(INT_MIN)보다 크므로 통과, 스택에 push → 스택: [40]
30: 40보다 작지만 루트(INT_MIN)보다는 크므로 통과, push → 스택: [40, 30]
35: 30보다 크므로 30을 pop하여 루트=30으로 갱신, push → 스택: [40, 35]
80: 35와 40보다 크므로 두 요소를 모두 pop, 마지막에 꺼낸 40이 루트가 됨, push → 스택: [80]
100: 80보다 크므로 80을 pop하여 루트=80으로 갱신, push → 스택: [100]

모든 단계에서 BST의 성질이 유지되었으므로 최종적으로 true가 반환됩니다. 만약 수열 중간에 루트보다 작은 값이 등장한다면 그 즉시 false를 반환하게 됩니다.

이 알고리즘의 시간 복잡도는 각 요소가 최대 한 번 push되고 한 번 pop되므로 O(n), 공간 복잡도는 스택 사용량에 비례하여 최악의 경우 O(n)입니다.