C++로 구현하는 이진 트리의 최대 BST 하위 트리 합계 찾기

이 튜토리얼에서는 이진 트리(Binary Tree)에서 하위 트리(sub-tree)가 동시에 BST(이진 탐색 트리)인 경우 중, 합계가 가장 큰 하위 트리의 합을 구하는 프로그램을 다룹니다.

하나의 이진 트리가 주어지며, 우리의 목표는 그 트리를 구성하는 하위 트리 중 BST 조건을 만족하는 것들만 골라내어, 그중 합이 가장 큰 하위 트리의 합계를 출력하는 것입니다.

접근 방법

이 문제는 후위 순회(postorder traversal)를 활용하면 효율적으로 해결할 수 있습니다. 각 노드를 기준으로 왼쪽과 오른쪽 자식 서브트리의 정보를 먼저 수집한 뒤, 현재 노드를 포함한 전체 서브트리가 BST인지 판별합니다.

이를 위해 다음 정보를 담는 Info 구조체를 사용합니다.

max / min: 해당 서브트리 내 최댓값과 최솟값
isBST: 해당 서브트리가 BST인지 여부
sum: 해당 서브트리의 노드 값 총합
currmax: 지금까지 발견된 BST 서브트리 합계의 최댓값

현재 노드를 루트로 하는 서브트리가 BST가 되려면 왼쪽 서브트리와 오른쪽 서브트리가 모두 BST여야 하고, 왼쪽 서브트리의 최댓값은 현재 노드의 값보다 작으며, 오른쪽 서브트리의 최솟값은 현재 노드의 값보다 커야 합니다. 조건을 만족하면 세 부분의 합을 계산해 전역 최댓값과 비교·갱신합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 이진 트리 노드 정의
struct Node {
   struct Node* left; struct Node* right; int data;
   Node(int data) {
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
struct Info {
   int max;
   int min;
   bool isBST;
   int sum;
   int currmax;
};
Info MaxSumBSTUtil(struct Node* root, int& maxsum) {
   if (root == NULL) return { INT_MIN, INT_MAX, true, 0, 0 };
   if (root->left == NULL && root->right == NULL) {
      maxsum = max(maxsum, root->data);
      return { root->data, root->data, true, root->data, maxsum };
   }
   Info L = MaxSumBSTUtil(root->left, maxsum);
   Info R = MaxSumBSTUtil(root->right, maxsum);
   Info BST;
   if (L.isBST && R.isBST && L.max < root->data && R.min > root->data) {
      BST.max = max(root->data, max(L.max, R.max));
      BST.min = min(root->data, min(L.min, R.min));
      maxsum = max(maxsum, R.sum + root->data + L.sum);
      BST.sum = R.sum + root->data + L.sum;
      BST.currmax = maxsum;
      BST.isBST = true;
      return BST;
   }
   BST.isBST = false;
   BST.currmax = maxsum;
   BST.sum = R.sum + root->data + L.sum;
   return BST;
}
int MaxSumBST(struct Node* root) {
   int maxsum = INT_MIN;
   return MaxSumBSTUtil(root, maxsum).currmax;
}
int main() {
   struct Node* root = new Node(5);
   root->left = new Node(14);
   root->right = new Node(3);
   root->left->left = new Node(6);
   root->right->right = new Node(7);
   root->left->left->left = new Node(9);
   root->left->left->right = new Node(1);
   cout << MaxSumBST(root);
   return 0;
}

실행 결과

결과 해설

예제 트리에서 루트 노드는 5이지만, 왼쪽 자식 14가 루트보다 크므로 전체 트리는 BST가 아닙니다. 반면 오른쪽 서브트리는 노드 3을 루트로 하고 자식 7을 가지는데, 3 < 7 관계가 성립하므로 유효한 BST입니다. 이 서브트리의 합은 3 + 7 = 10이 되어, 다른 BST 서브트리(예: 단일 노드 9의 합 9)보다 큰 최댓값이 됩니다.

정리

이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다. 재귀 호출을 통해 각 서브트리의 최솟값, 최댓값, BST 여부, 합계를 bottom-up 방식으로 전달하기 때문에 추가적인 검증 과정 없이 최대 합계를 효율적으로 구할 수 있습니다.