C++로 이진 탐색 트리의 전위 순회 순서 검증하기

문제 개요

숫자로 이루어진 수열이 하나 주어졌을 때, 이 수열이 어떤 이진 탐색 트리(Binary Search Tree, BST)의 올바른 전위 순회(preorder traversal) 결과인지 판별하는 문제입니다. 수열에 포함된 각 숫자는 모두 고유하다고 가정할 수 있습니다.

예를 들어 다음과 같은 이진 탐색 트리가 있다고 가정해 보겠습니다.

이 트리를 전위 순회하면 [5, 2, 1, 3, 6]이 되므로, 입력이 [5, 2, 1, 3, 6]일 때의 출력은 true입니다.

접근 방법

전위 순회의 핵심 성질을 활용합니다. 전위 순회는 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문하기 때문에, 어떤 노드보다 큰 값이 처음 등장하는 순간 그 이후의 값들은 모두 해당 노드의 오른쪽 서브트리에 속하게 됩니다. 따라서 지금까지 지나온 값 중 마지막으로 꺼낸 값을 하한선(low)으로 기록해 두면, 이후 등장하는 모든 값은 반드시 이 하한선보다 커야 합니다.

스택을 활용한 알고리즘은 다음과 같습니다.

itr을 -1로, low를 음의 무한대(-∞)로 초기화합니다.
i를 0부터 preorder 배열의 끝까지 반복합니다.
- x = preorder[i]를 가져옵니다.
- 만약 x < low라면 유효하지 않은 수열이므로 false를 반환합니다.
- itr >= 0이면서 preorder[itr] < x인 동안, 스택에서 값을 꺼내듯 low를 갱신하고 itr을 감소시킵니다.
- itr을 1 증가시킨 뒤 preorder[itr]에 x를 저장합니다(스택에 push하는 것과 동일).
모든 원소를 통과하면 true를 반환합니다.

눈여겨볼 점은 별도의 스택 자료구조를 새로 만들지 않고 입력 배열 자체를 스택처럼 재활용한다는 것입니다. 덕분에 추가 공간 없이 선형 시간 안에 문제를 해결할 수 있습니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int itr = -1;
        int low = INT_MIN;
        for (int i = 0; i < preorder.size(); i++) {
            int x = preorder[i];
            if (x < low)
                return false;
            while (itr >= 0 && preorder[itr] < x) {
                low = preorder[itr];
                itr--;
            }
            itr++;
            preorder[itr] = x;
        }
        return true;
    }
};

main(){
    Solution ob;
    vector<int> v = {5,2,1,3,6};
    cout << (ob.verifyPreorder(v));
}

입력

{5,2,1,3,6}

출력

복잡도 분석

시간 복잡도: O(n) — 각 원소는 최대 한 번 push되고 한 번 pop되므로 전체 연산 횟수는 배열 길이에 비례합니다.
공간 복잡도: O(1) — 입력 배열을 그대로 스택으로 활용하므로 별도의 추가 공간이 필요하지 않습니다.