C++로 BST 전위 순회 결과에서 루트보다 작은 요소 개수 구하기

이진 탐색 트리(BST)의 전위 순회(preorder traversal) 결과가 주어졌을 때, 루트보다 작은 요소의 개수를 찾는 문제를 다뤄보겠습니다.

전위 순회에서는 트리의 루트를 가장 먼저 방문하기 때문에, 순회 결과의 첫 번째 요소가 곧 BST의 루트입니다. 이 특성만 활용하면 간단하게 해결할 수 있습니다. 예제를 통해 살펴보겠습니다.

입력

preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]

출력

루트는 첫 번째 요소인 5이며, 5보다 작은 요소는 4, 2, 1로 총 3개입니다.

알고리즘

전위 순회 결과를 배열에 저장합니다.
첫 번째 요소, 즉 BST의 루트를 변수에 따로 저장해 둡니다.
배열의 두 번째 요소부터 끝까지 반복문을 돌립니다.
- 현재 요소를 루트 값과 비교합니다.
- 현재 요소가 루트보다 작으면 카운트를 1 증가시킵니다.
최종 카운트를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

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

int getElementsCount(int arr[], int n) {
    if (n <= 0) {
        return 0;
    }
    int i, root = arr[0], count = 0;
    for (i = 1; i < n; i++) {
        if (arr[i] < root) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
    int n = sizeof(preorder) / sizeof(preorder[0]);
    cout << getElementsCount(preorder, n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

복잡도 분석

시간 복잡도: O(n) — 배열의 모든 요소를 한 번씩 순회합니다.
공간 복잡도: O(1) — 추가적인 메모리 사용 없이 상수 공간만 필요합니다.