문제 개요
이 문제에서는 두 개의 이진 탐색 트리(Binary Search Tree)가 주어지며, 두 트리에 공통으로 존재하는 노드를 찾아 출력하는 것이 목표입니다.
이진 트리(Binary Tree)는 모든 노드가 최대 두 개의 자식 노드를 가질 수 있는 특수한 형태의 트리입니다. 즉, 각 노드는 자식이 없는 리프 노드이거나, 한 개 또는 두 개의 자식 노드를 갖습니다.
예시:
위 그림처럼 두 개의 이진 트리가 주어졌을 때, 두 트리 모두에서 동일한 값을 가지는 모든 노드를 출력해야 합니다.
접근 방법: 보조 스택 활용
보조 스택(auxiliary stack)을 사용하면 이 문제를 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 재귀 호출 대신 스택을 이용해 두 트리를 동시에 중위 순회(inorder traversal)합니다.
- 중위 순회는 이진 탐색 트리의 값을 오름차순으로 방문하므로, 두 트리의 값을 마치 정렬된 두 배열을 비교하는 것처럼 처리할 수 있습니다.
- 두 스택의 최상단(top) 값이 서로 같으면 공통 노드이므로 이를 출력하고, 양쪽 스택에서 요소를 제거(pop)한 뒤 각각 오른쪽 서브트리로 이동합니다.
- 한쪽 값이 더 작다면 작은 쪽 스택만 pop하고 해당 트리의 오른쪽 서브트리로 진행해 두 값을 맞춰 나갑니다.
C++ 구현 코드
#include<iostream>
#include<stack>
using namespace std;
struct Node{
int key;
struct Node *left, *right;
};
Node *newNode(int ele){
Node *temp = new Node;
temp->key = ele;
temp->left = temp->right = NULL;
return temp;
}
void printCommon(Node *tree1, Node *tree2){
stack<Node *> stack1, s1, s2;
while (1){
if (tree1){
s1.push(tree1);
tree1 = tree1->left;
}
else if (tree2){
s2.push(tree2);
tree2 = tree2->left;
}
else if (!s1.empty() && !s2.empty()){
tree1 = s1.top();
tree2 = s2.top();
if (tree1->key == tree2->key){
cout << tree1->key << " ";
s1.pop();
s2.pop();
tree1 = tree1->right;
tree2 = tree2->right;
}
else if (tree1->key < tree2->key){
s1.pop();
tree1 = tree1->right;
tree2 = NULL;
}
else if (tree1->key > tree2->key){
s2.pop();
tree2 = tree2->right;
tree1 = NULL;
}
}
else break;
}
}
void inorderTraversal(struct Node *root){
if (root){
inorderTraversal(root->left);
cout<<root->key<<" ";
inorderTraversal(root->right);
}
}
struct Node* insertNode(struct Node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
int main(){
Node *tree1 = NULL;
tree1=insertNode(tree1, 45);
tree1=insertNode(tree1, 87);
tree1=insertNode(tree1, 12);
tree1=insertNode(tree1, 54);
tree1=insertNode(tree1, 89);
tree1=insertNode(tree1, 19);
tree1=insertNode(tree1, 72);
cout<<"Binary Tree 1 : ";
inorderTraversal(tree1);
cout<<endl;
Node *tree2=NULL;
tree2=insertNode(tree2, 72);
tree2=insertNode(tree2, 23);
tree2=insertNode(tree2, 13);
tree2=insertNode(tree2, 1);
tree2=insertNode(tree2, 19);
cout<<"Binary Tree 2 : ";
inorderTraversal(tree2);
cout<<endl;
cout<<"Common Nodes between the two trees : ";
printCommon(tree1, tree2);
return 0;
}실행 결과
Binary Tree 1 : 12 19 45 54 72 87 89 Binary Tree 2 : 1 13 19 23 72 Common Nodes between the two trees : 19 72
첫 번째 트리의 중위 순회 결과는 12 19 45 54 72 87 89이고, 두 번째 트리는 1 13 19 23 72입니다. 실행 결과에서 확인할 수 있듯이, 두 트리에 공통으로 존재하는 노드는 19와 72입니다.
복잡도 분석
- 시간 복잡도: O(n + m) — n과 m은 각각 두 트리의 노드 개수입니다. 각 노드를 최대 한 번씩만 방문하므로 매우 효율적입니다.
- 공간 복잡도: O(h1 + h2) — h1과 h2는 각 트리의 높이입니다. 스택에는 트리의 높이에 비례하는 만큼의 노드만 저장됩니다.