C++로 풀어보는 이진 트리 문제: BST 조건을 만족하는 최대 하위 트리 합 구하기

이번 문제에서는 하나의 이진 트리(Binary Tree)가 주어졌을 때, 그 하위 트리(subtree)가 동시에 이진 탐색 트리(BST)를 이루는 경우 중 노드 값의 합이 가장 큰 하위 트리를 찾는 프로그램을 만드는 것이 목표입니다.

기본 개념 정리

이진 트리는 각 노드가 최대 두 개의 자식 노드만 가질 수 있는 특수한 트리 구조입니다.

이진 탐색 트리(BST)는 모든 노드가 다음 두 가지 성질을 만족하는 트리를 말합니다.

왼쪽 하위 트리에 속한 모든 키 값은 부모(루트) 노드의 키 값보다 작아야 합니다.
오른쪽 하위 트리에 속한 모든 키 값은 부모(루트) 노드의 키 값보다 크거나 같아야 합니다.

문제 이해를 위한 예시

입력

다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.

출력

설명

이 트리에서 BST 조건을 만족하는 하위 트리는 두 개입니다. 각각의 합은 다음과 같습니다.

7 + 3 + 22 = 32
6 + 5 + 17 = 28
최댓값 = 32

따라서 정답은 32가 됩니다.

해결 접근 방법

가장 직관적인 해결 방법은 트리 전체를 순회하면서 각 노드를 기준으로 해당 노드와 자식들이 BST를 형성할 수 있는지 확인하는 것입니다. BST를 형성하는 경우 그 하위 트리에 포함된 모든 노드의 합을 계산하고, 지금까지 발견된 BST 합들 중 최댓값을 반환하면 됩니다.

효율적인 구현을 위해 재귀적으로 하위 트리 정보를 아래에서 위로 전달하는 방식(후위 순회)을 사용합니다. 각 노드마다 다음 정보를 함께 관리합니다.

하위 트리 내 최댓값(maxVal)
하위 트리 내 최솟값(minVal)
BST 여부(isBST)
하위 트리의 노드 합(sum)

C++ 구현 예제

아래 프로그램은 위 접근 방법을 실제로 구현한 코드입니다.

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

int findMax(int a, int b){
    if(a > b)
    return a;
    return b;
}
int findMin(int a, int b){
    if(a > b)
    return b;
    return a;
}
struct Node {
    struct Node* left;
    struct Node* right;
    int data;
    Node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
struct treeVal{
    int maxVal;
    int minVal;
    bool isBST;
    int sum;
    int currMax;
};
treeVal CalcBSTSumTill(struct Node* root, int& maxsum){
    if (root == NULL)
    return { -10000, 10000, true, 0, 0 };
    if (root->left == NULL && root->right == NULL) {
        maxsum = findMax(maxsum, root->data);
        return { root->data, root->data, true, root->data, maxsum };
    }
    treeVal LeftSTree = CalcBSTSumTill(root->left, maxsum);
    treeVal RightSTree = CalcBSTSumTill(root->right, maxsum);
    treeVal currTRee;
    if (LeftSTree.isBST && RightSTree.isBST && LeftSTree.maxVal <
    root->data && RightSTree.minVal > root->data) {
        currTRee.maxVal = findMax(root->data,
        findMax(LeftSTree.maxVal, RightSTree.maxVal));
        currTRee.minVal = findMin(root->data,
        findMin(LeftSTree.minVal, RightSTree.minVal));
        maxsum = findMax(maxsum, RightSTree.sum + root->data +
        LeftSTree.sum);
        currTRee.sum = RightSTree.sum + root->data +
        LeftSTree.sum;
        currTRee.currMax = maxsum;
        currTRee.isBST = true;
        return currTRee;
    }
    currTRee.isBST = false;
    currTRee.currMax = maxsum;
    currTRee.sum = RightSTree.sum + root->data + LeftSTree.sum;
    return currTRee;
}
int CalcMaxSumBST(struct Node* root){
    int maxsum = -10000;
    return CalcBSTSumTill(root, maxsum).currMax;
}
int main(){
    struct Node* root = new Node(10);
    root->left = new Node(12);
    root->left->right = new Node(7);
    root->left->right->left = new Node(3);
    root->left->right->right = new Node(22);
    root->right = new Node(6);
    root->right->left = new Node(5);
    root->right->left->right = new Node(17);
    cout<<"BST인 하위 트리 중 최대 합은 "<<CalcMaxSumBST(root);
    return 0;
}

실행 결과

BST인 하위 트리 중 최대 합은 32

마무리

이 알고리즘은 트리의 각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다. 재귀 호출에 따른 스택 공간 때문에 공간 복잡도는 트리의 높이에 비례하여 최악의 경우 O(N)이 됩니다. 후위 순회 기반으로 하위 트리의 최댓값, 최솟값, 합계 정보를 상위 노드로 전달하는 패턴은 BST 관련 다양한 트리 문제에서도 유용하게 활용되니 잘 기억해 두시길 바랍니다.