View in English →

Code › algorithm-study

LeetCode 938 - Range Sum of BST

BST range sum 문제를 BFS, DFS, prefix sum 관점에서 정리한 풀이

algorithmleetcodebsttreebfsdfscpplearning

이 문제는 Easy 난이도의 이진 탐색 트리 문제다. low와 high 사이에 들어오는 노드 값의 합을 구하는 문제이고, 겉으로는 단순한 트리 순회처럼 보인다. 이번 글에서는 BFS로 시작한 풀이를 BST pruning과 공간복잡도 관점에서 다시 정리했다.

문제 링크 & 설명

  • 문제 링크: 938. Range Sum of BST
  • 요약: 이진 탐색 트리(BST)의 루트 노드와 low, high가 주어졌을 때, 값이 low 이상 high 이하인 모든 노드의 합을 구하는 문제다.

예를 들어 이런 트리가 있다고 해보자.

       6
      / \
     4   8
    / \ / \
   3  5 7  9
  /
 2

범위가 [2, 5]라면 포함되는 값은 2, 3, 4, 5이고 합은 14가 된다. 범위가 [6, 6]이라면 6만 포함되므로 결과도 6이다.

BST는 왼쪽 서브트리의 값이 현재 노드보다 작고, 오른쪽 서브트리의 값이 현재 노드보다 큰 구조다. 그래서 모든 노드를 무조건 확인하지 않아도 된다. 현재 노드 값이 low보다 작으면 왼쪽은 더 작으니 볼 필요가 없고, 현재 노드 값이 high보다 크면 오른쪽은 더 크니 마찬가지로 건너뛸 수 있다.

접근 방법

처음에는 BFS가 먼저 떠올랐고, 큐에 루트를 넣고 하나씩 꺼내면서 현재 노드 값이 범위 안에 있을 때만 합산하면 되는 방식이라 구현도 직관적이었다.

가장 단순하게는 모든 노드를 BFS로 순회할 수 있다. 예제 트리 기준으로 방문 순서는 대략 이런 식이다.

6 -> 4 -> 8 -> 3 -> 5 -> 7 -> 9 -> 2

이렇게 풀어도 정답은 나오지만, 이 방식은 BST가 아니라 일반 이진 트리여도 똑같이 동작한다. 왼쪽은 작고 오른쪽은 크다는 정보를 전혀 쓰지 않기 때문이다.

그래서 다음 단계로 BST의 성질을 이용해 pruning을 넣었다. 현재 노드 값이 low보다 크다면 왼쪽 서브트리에 아직 범위에 들어올 값이 있을 수 있고, 현재 노드 값이 high보다 작다면 오른쪽 서브트리에도 범위에 들어올 값이 있을 수 있다.

반대로 현재 노드 값이 low보다 작거나 같으면 왼쪽은 더 작으니 볼 필요가 없고, 현재 노드 값이 high보다 크거나 같으면 오른쪽은 더 크니 볼 필요가 없다. 큐에 넣는 순간부터 가지치기(pruning)를 하는 셈이다.

#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;

        int total = 0;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (low <= node->val && node->val <= high) {
                total += node->val;
            }

            if (node->left && node->val > low) {
                q.push(node->left);
            }

            if (node->right && node->val < high) {
                q.push(node->right);
            }
        }

        return total;
    }
};

여기서 중요한 조건은 이 두 줄이다.

if (node->left && node->val > low) q.push(node->left);
if (node->right && node->val < high) q.push(node->right);

왼쪽으로 갈지 말지는 현재 값이 low보다 큰지로 판단하고, 오른쪽으로 갈지 말지는 현재 값이 high보다 작은지로 판단한다. 처음에는 순회 방식 자체에 집중했는데, 실제로는 이 조건이 문제의 핵심에 더 가까웠다.

트러블 슈팅

BFS로 풀었을 때의 공간복잡도

pruning을 넣어도 최악의 경우 시간복잡도는 여전히 O(n)이다. 범위가 넓거나 트리 구조상 대부분의 노드를 봐야 하면 결국 많은 노드를 방문하게 되는데, 여기까지는 크게 이상할 게 없었다.

문제는 공간복잡도였다. BFS는 큐를 쓰고, 큐에는 같은 레벨의 노드들이 한꺼번에 쌓일 수 있다. 균형 잡힌 이진 트리를 생각하면 아래로 내려갈수록 한 레벨의 노드 수가 대략 두 배씩 늘어난다.

level 0: 1개
level 1: 2개
level 2: 4개
level 3: 8개

노드가 15개인 완전 이진 트리라면 마지막 레벨에만 8개의 노드가 있다. 전체 노드 수가 15개인데 마지막 레벨이 8개니까 거의 n / 2에 가깝다. BFS는 위 레벨을 처리하면서 그 아래 레벨의 노드들을 큐에 계속 넣기 때문에, 어느 순간 큐 안에 마지막 레벨 근처의 노드들이 많이 쌓일 수 있다.

그래서 균형 잡힌 트리에서 BFS의 공간복잡도는 O(n)까지 커진다. n / 2라고 해도 빅오에서는 상수를 버리니까 결국 O(n)이다.

O(n)을 실제 메모리로 생각해보기

알고리즘 문제에서는 O(n) 공간복잡도가 자주 나오지만, n이 100억 개라면 같은 표기라도 검토해야 할 내용이 달라진다. 큐에 노드 포인터만 100억 개 들어간다고 해도, 포인터 하나를 8바이트로 잡으면 대략 80GB가 필요하다.

10,000,000,000 * 8 bytes
= 80,000,000,000 bytes
≈ 80 GB

이건 큐 안에 들어가는 참조만 단순하게 계산한 것이다. 실제 노드 객체, 컨테이너 오버헤드, 런타임 메모리까지 생각하면 더 커질 수 있다. 그러니까 현업에서 O(n) 공간복잡도는 그냥 “선형이네”로 끝낼 문제가 아니라, 그 n이 실제로 얼마나 큰지와 무엇을 들고 있는지를 같이 봐야 한다.

반복 요청이 많을 때의 다른 질문

트리가 매우 크고, 같은 함수가 반복해서 호출된다고 생각하면 이야기가 또 달라진다. 예를 들어 트리는 고정되어 있는데 low, high 범위 합 요청이 계속 들어온다면, 매 요청마다 트리를 탐색하는 방식 자체가 부담이 될 수 있다.

이 조건에서는 inorder 순회와 prefix sum을 생각해볼 수 있다. BST는 inorder 순회를 하면 값이 정렬된 순서로 나오기 때문에, 트리가 고정되어 있다면 한 번 순회해서 정렬된 배열을 만들고 그 위에 prefix sum을 미리 계산해둘 수 있다.

values: [2, 3, 4, 5, 6, 7, 8, 9]
prefix: [0, 2, 5, 9, 14, 20, 27, 35, 44]

그다음 low, high 요청이 들어오면 low 이상이 처음 나오는 위치와 high보다 큰 값이 처음 나오는 위치를 이진 탐색으로 찾고, prefix sum의 차이를 계산하면 된다.

left = lower_bound(values, low)
right = upper_bound(values, high)
answer = prefix[right] - prefix[left]

이 방식은 매번 트리를 다시 도는 비용을 전처리 비용으로 옮긴다. 전처리는 O(n)이고 추가 공간도 O(n)이지만, 트리가 고정되어 있고 범위 합 요청이 많다면 각 요청을 O(log n)으로 처리할 수 있다. 다만 이건 LeetCode 단일 호출 풀이의 개선이라기보다, 같은 데이터에 range query가 반복되는 시스템 상황에서의 최적화에 가깝다.

다만 이 방식은 입력 데이터가 고정되어 있다는 전제가 강하다. 값이 추가되거나 삭제된다면 정렬된 배열을 다시 맞추고 prefix sum도 다시 계산해야 하는데, 변경이 잦은 데이터에서는 이 비용이 부담이 된다. 이 경우에는 알고리즘 문제를 넘어 데이터베이스 인덱스 구조 쪽을 살펴보면 좋다.

변경이 잦은 데이터에서 range query를 다루려면 B+ tree 같은 구조를 생각할 수 있다. B+ tree는 한 노드에 키 하나만 두는 일반 BST와 다르게, 페이지 단위 노드 하나에 여러 키와 자식 포인터를 함께 저장한다. 그래서 같은 데이터 개수라도 트리 높이가 낮아지고, 실제 데이터는 leaf level에 정렬된 상태로 이어진다. 탐색할 때는 루트에서 필요한 leaf까지 내려가고, 범위 탐색은 연결된 leaf를 따라가면 된다. 전체 데이터를 한 번에 큐나 스택에 올리는 방식이 아니라 필요한 경로와 필요한 leaf page만 다루기 때문에, 작업 중 메모리 사용량과 디스크 접근을 더 예측하기 쉽다. 다만 range sum 자체를 더 빠르게 하려면 각 페이지나 서브트리에 부분합 같은 메타데이터를 추가로 들고 있어야 한다.

이 부분은 별도 데이터베이스 시리즈 글로 정리해볼 생각이다.

복잡도 분석

1. BFS + pruning

  • 시간 복잡도: O(n)

    • pruning으로 일부 서브트리를 건너뛸 수 있지만, 범위가 넓거나 트리 구조상 대부분의 노드를 봐야 하면 최악의 경우 모든 노드를 방문한다.

  • 공간 복잡도: O(width), 최악의 경우 O(n)

    • BFS는 큐에 같은 레벨의 노드를 담는다. 균형 잡힌 트리에서는 마지막 레벨 근처의 노드 수가 전체 노드 수의 절반 가까이 될 수 있으므로, 최악의 경우 O(n)까지 커진다.

2. DFS + pruning

  • 시간 복잡도: O(n)

    • BFS와 마찬가지로 최악의 경우 모든 노드를 볼 수 있다. 다만 BST의 범위를 이용해 불필요한 서브트리를 건너뛸 수 있다.

  • 공간 복잡도: O(h)

    • DFS는 현재 내려가는 경로만 호출 스택에 쌓인다. 균형 잡힌 트리라면 h = log n이므로 추가 스택은 O(log n)으로 볼 수 있지만, 한쪽으로 치우친 편향 트리라면 링크드 리스트와 비슷해져 O(n)까지 깊어진다. 이 경우 BST search 자체도 O(n)이 되고, 입력이 충분히 크면 호출 스택이 선형으로 늘어나면서 stack overflow가 날 수도 있다.

이 문제의 단일 호출 풀이로는 DFS + pruning이 가장 자연스럽다. 균형 잡힌 트리라면 BFS처럼 한 레벨의 노드를 큐에 많이 들고 있을 필요가 없고, 현재 경로만 들고 내려가면 되기 때문이다. 다만 LeetCode 입력 트리는 이미 주어진 구조라서, 풀이 중에 트리를 AVL tree나 Red-Black tree로 바꾸는 문제는 아니다. 여기서는 편향 트리라면 DFS도 O(n) 스택을 쓸 수 있다는 점을 복잡도에 반영하는 정도가 맞다.

반대로 내가 직접 BST 자료구조를 설계하고 오래 유지하는 상황이라면 이야기가 달라진다. 이때는 편향을 막기 위해 AVL tree나 Red-Black tree 같은 self-balancing BST를 쓰는 편이 더 적합하다. 트리 높이를 O(log n) 수준으로 유지해 search와 DFS 경로 길이를 안정적으로 제한할 수 있기 때문이다. 그래도 전체 저장 공간은 여전히 노드 n개에 비례한다.

3. 시스템 관점, 고정 데이터 + prefix sum

  • 전처리: O(n)

    • inorder 순회로 정렬된 배열을 만들고 prefix sum 배열을 계산한다.

  • 공간 복잡도: O(n)

    • 정렬된 값 배열과 prefix sum 배열을 별도로 들고 있어야 한다.

  • 쿼리 복잡도: O(log n)

    • low와 high의 위치를 이진 탐색으로 찾고, prefix sum의 차이를 계산한다. 입력 데이터가 고정되어 있고 range sum 요청이 반복되는 시스템이라면 이 방식이 단순하면서도 빠르다. 대신 값이 자주 바뀌면 배열과 prefix sum을 다시 맞추는 비용이 커진다.

4. 시스템 관점, 데이터가 계속 바뀌는 경우 + B+ tree

prefix sum 방식은 빠르지만, 정렬된 값 배열과 prefix sum 배열을 메모리에 따로 들고 있어야 한다. 데이터가 고정되어 있다면 괜찮지만, 값이 계속 추가되거나 삭제되면 배열의 순서와 누적합을 다시 맞추는 비용이 커진다.

B+ tree는 이 지점에서 다른 선택지가 된다. 전체 데이터를 평탄화 배열로 한 번에 들고 계산하는 대신, 페이지 단위 노드와 leaf page를 따라 필요한 구간만 읽는다. 전체 데이터 저장 공간이 사라지는 것은 아니지만, 한 번의 range query에서 실제로 메모리에 올려 다루는 범위는 루트에서 leaf까지의 경로와 필요한 leaf page 중심으로 줄어든다. 그래서 prefix sum 배열처럼 전체 누적합을 별도로 들고 있는 방식보다, 데이터가 크고 변경이 계속되는 상황에서 작업 중 메모리 사용량과 디스크 접근 패턴을 더 예측하기 쉽다.

다만 B+ tree만으로 range sum이 자동으로 빠르게 계산되는 것은 아니다. 합계를 빠르게 구하려면 leaf page나 서브트리에 부분합 같은 메타데이터를 따로 관리해야 한다. 이 부분은 LeetCode 풀이보다 데이터베이스 인덱스 설계에 가까우니, 여기서는 방향만 잡고 넘어간다.

최적화 코드

위의 흐름을 바탕으로 최종적으로는 DFS와 BST pruning을 함께 쓰는 방식이 더 적합하다고 정리했다.

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;

        if (root->val < low) {
            return rangeSumBST(root->right, low, high);
        }

        if (root->val > high) {
            return rangeSumBST(root->left, low, high);
        }

        return root->val
            + rangeSumBST(root->left, low, high)
            + rangeSumBST(root->right, low, high);
    }
};

현재 노드 값이 low보다 작으면 왼쪽 서브트리는 더 작으니 오른쪽만 보면 되고, 현재 노드 값이 high보다 크면 오른쪽 서브트리는 더 크니 왼쪽만 보면 된다. 현재 노드가 범위 안에 있을 때만 양쪽을 모두 확인하면서 값을 더한다.

요약 및 회고

BFS로 먼저 정답을 만든 뒤 공간복잡도 기준으로 다시 검토해보니, LeetCode 단일 호출 풀이에서는 DFS + pruning이 더 자연스럽다는 점이 분명해졌다. 처음에는 “어차피 필요한 노드만 보면 되는 거 아닌가” 정도로 생각했는데, BFS는 큐에 같은 레벨의 노드를 많이 들고 있을 수 있고 DFS는 호출 스택에 현재 경로를 들고 내려간다. 이 차이는 입력이 커질수록 훨씬 크게 드러난다.

다만 이 글에서 다룬 최적화들은 층위가 다르다. 알고리즘 문제의 답은 DFS + pruning이고, 내가 자료구조 자체를 설계할 수 있다면 편향을 막기 위해 AVL tree나 Red-Black tree를 고려하는 쪽이 맞다. 반면 prefix sum과 B+ tree는 같은 range sum 요청이 반복되는 시스템 상황에서의 최적화다. 결국 range sum은 단일 함수 호출에서는 순회 방식의 문제지만, 시스템으로 커지면 데이터가 어떻게 저장되고, 얼마나 자주 바뀌며, 어떤 형태로 반복 조회되는지까지 같이 봐야 하는 문제가 된다.