C++로 이진 트리에 크기 2 이상의 중복 서브트리가 있는지 확인하는 방법

이진 트리가 하나 주어졌다고 가정해 보겠습니다. 이때 확인해야 할 것은 해당 트리 안에 크기가 2 이상인 중복된 서브트리(하위 트리)가 존재하는지 여부입니다. 예를 들어 다음과 같은 이진 트리가 있다고 합시다.

위 트리에는 크기가 2인 완전히 동일한 서브트리가 두 개 존재합니다. 이 문제는 트리 직렬화(serialization)와 해싱(hashing) 기법을 함께 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 서브트리를 문자열 형태로 직렬화한 뒤 해시 테이블(집합)에 저장하고, 리프 노드가 아닌 어떤 서브트리의 직렬화 결과가 이미 해시 테이블에 존재한다면 중복이 있다는 사실을 즉시 반환하는 것입니다.

동작 원리

루트부터 재귀적으로 트리를 순회하면서 각 서브트리를 문자열로 직렬화합니다.
NULL 자식 노드는 '$' 마커로 표현해 트리의 구조적 정보를 그대로 문자열에 담습니다.
직렬화된 문자열의 길이가 3보다 큰 경우, 즉 단일 리프 노드가 아닌 서브트리만 해시 집합에 저장합니다.
순회 중 동일한 직렬화 문자열이 이미 집합에 존재하면 크기 2 이상의 중복 서브트리가 있다는 뜻이므로, 빈 문자열을 반환해 상위 호출부로 결과를 전달합니다.

예제 코드

#include <iostream>
#include <unordered_set>
using namespace std;

const char MARKER = '$';

struct Node {
    char key;
    Node *left, *right;
};

Node* getNode(char key) {
    Node* newNode = new Node;
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

unordered_set<string> subtrees;

string duplicateSubtreeFind(Node *root) {
    string res = "";
    if (root == NULL) // 현재 노드가 NULL이면 마커 반환
        return res + MARKER;
    string l_Str = duplicateSubtreeFind(root->left);
    if (l_Str.compare(res) == 0) // 왼쪽에서 중복이 발견되면 즉시 전파
        return res;
    string r_Str = duplicateSubtreeFind(root->right);
    if (r_Str.compare(res) == 0) // 오른쪽에서 중복이 발견되면 즉시 전파
        return res;
    res = res + root->key + l_Str + r_Str;
    // 리프가 아닌 서브트리가 이미 존재하면 중복이므로 빈 문자열 반환
    if (res.length() > 3 && subtrees.find(res) != subtrees.end())
        return "";
    subtrees.insert(res);
    return res;
}

int main() {
    Node *root = getNode('A');
    root->left = getNode('B');
    root->right = getNode('C');
    root->left->left = getNode('D');
    root->left->right = getNode('E');
    root->right->right = getNode('B');
    root->right->right->right = getNode('E');
    root->right->right->left = getNode('D');

    string str = duplicateSubtreeFind(root);
    if (str.compare("") == 0)
        cout << "It has duplicate subtrees of size more than 1";
    else
        cout << "It has no duplicate subtrees of size more than 1";
}

출력 결과

It has duplicate subtrees of size more than 1

정리

이 방식은 트리 전체를 한 번씩만 순회하면 되므로 시간 복잡도는 O(n)이며, 직렬화 문자열을 해시 집합에 저장하므로 공간 복잡도 역시 O(n) 수준입니다. 서브트리를 고유한 문자열로 변환해 비교한다는 점만 이해하면, 구조가 완전히 같은 서브트리가 존재하는지 손쉽게 판별할 수 있습니다.