C++에서 한 이진 트리가 다른 이진 트리의 서브트리인지 확인하는 방법

두 개의 이진 트리가 주어졌을 때, 그중 작은 트리가 다른 큰 트리의 서브트리(subtree)인지 판별하는 문제를 살펴보겠습니다. 아래와 같은 두 개의 트리가 있다고 가정해 봅시다.

문제 접근 방식

위 그림에서 두 번째 트리는 첫 번째 트리의 서브트리입니다. 이 성질을 확인하려면 다음과 같은 절차를 따릅니다.

먼저 메인 트리를 후위 순회(post-order) 방식으로 탐색하면서 각 노드를 방문합니다. 그리고 현재 방문한 노드를 루트로 하는 부분 트리가 두 번째 트리와 완전히 동일한 구조와 값을 갖는지 비교합니다. 만약 어느 한 지점에서 두 트리가 일치한다면, 두 번째 트리는 첫 번째 트리의 서브트리라고 결론지을 수 있습니다.

이 알고리즘은 두 단계로 구성됩니다.

areTwoTreeSame(): 두 트리의 루트 노드 값이 같고, 왼쪽 서브트리끼리도 같으며, 오른쪽 서브트리끼리도 같은지 재귀적으로 검사하여 두 트리가 동일한지 판별합니다.
isSubtree(): 메인 트리의 각 노드를 기준으로 areTwoTreeSame()을 호출하고, 일치하지 않으면 왼쪽과 오른쪽 자식 서브트리에 대해 재귀적으로 탐색을 계속합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class node {
   public:
   int data;
   node *left, *right;
};
// 두 트리가 동일한지 재귀적으로 확인하는 함수
bool areTwoTreeSame(node * t1, node *t2) {
   if (t1 == NULL && t2 == NULL)
      return true;
   if (t1 == NULL || t2 == NULL)
      return false;
   return (t1->data == t2->data && areTwoTreeSame(t1->left, t2->left) && areTwoTreeSame(t1->right, t2->right) );
}
// sub_tree가 tree의 서브트리인지 확인하는 함수
bool isSubtree(node *tree, node *sub_tree) {
   if (sub_tree == NULL)
      return true;
   if (tree == NULL)
      return false;
   if (areTwoTreeSame(tree, sub_tree))
      return true;
   return isSubtree(tree->left, sub_tree) || isSubtree(tree->right, sub_tree);
}
// 새 노드를 생성하는 헬퍼 함수
node* getNode(int data) {
   node* newNode = new node();
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
int main() {
   // 첫 번째(메인) 트리 생성
   node *real_tree = getNode(26);
   real_tree->right = getNode(3);
   real_tree->right->right = getNode(3);
   real_tree->left = getNode(10);
   real_tree->left->left = getNode(4);
   real_tree->left->left->right = getNode(30);
   real_tree->left->right = getNode(6);
   // 두 번째(서브트리 후보) 트리 생성
   node *sub_tree = getNode(10);
   sub_tree->right = getNode(6);
   sub_tree->left = getNode(4);
   sub_tree->left->right = getNode(30);
   if (isSubtree(real_tree, sub_tree))
      cout << "Second tree is subtree of the first tree";
   else
      cout << "Second tree is not a subtree of the first tree";
}

실행 결과

Second tree is subtree of the first tree

시간 복잡도

이 방법의 시간 복잡도는 O(m × n)입니다. 여기서 m은 메인 트리의 노드 수, n은 서브트리 후보의 노드 수입니다. 메인 트리의 모든 노드마다 두 트리의 동일 여부를 검사하기 때문입니다.

참고로 빈 서브트리(NULL)는 어떤 트리의 서브트리로도 간주되어 true를 반환하며, 반대로 메인 트리가 비어 있는데 서브트리 후보가 존재하면 false를 반환합니다.