C++로 이진 트리에서 두 노드의 공통 조상(루트 경로 상의 공통 노드) 출력하기

문제 개요

이 문제에서는 하나의 이진 트리와 그 안의 두 노드가 주어지며, 루트에서 해당 노드까지 탐색하는 경로에 공통으로 등장하는 모든 노드, 즉 두 노드의 공통 조상(Common Ancestor)들을 출력해야 합니다.

이진 트리(Binary Tree)는 모든 노드가 최대 두 개의 자식 노드만 가질 수 있는 특수한 트리 구조입니다. 즉, 각 노드는 리프 노드이거나 한 개 또는 두 개의 자식 노드를 가집니다.

예시

핵심 용어 정리

조상 노드(Ancestor Node): 트리에서 자신보다 하위 레벨에 있는 노드들과 연결된 노드를 의미합니다.

공통 조상 노드(Common Ancestor Node): 두 노드가 주어졌을 때, 두 노드 모두의 조상이 되는 노드를 말합니다.

예시 −

위 이진 트리에서 노드 0과 노드 6의 공통 조상을 찾는다고 가정해 보겠습니다.

출력 − 3, 2

알고리즘

이 문제는 다음 두 단계로 해결할 수 있습니다.

Step 1 : 주어진 트리에서 두 노드의 최저 공통 조상(LCA, Lowest Common Ancestor)을 찾아 출력합니다.
Step 2 : 해당 지점부터 루트 노드까지 거슬러 올라가며 경로에 포함된 모든 노드를 순서대로 출력합니다.

C++ 구현 예제

이제 위 알고리즘을 실제로 구현한 프로그램을 살펴보겠습니다.

#include <iostream>
using namespace std;
struct Node {
   struct Node* left, *right;
   int key;
};
Node* insertNode(int key){
   Node* temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return temp;
}
struct Node* LowestCommonAncestors(struct Node* root, int n1, int n2){
   if (root == NULL)
      return NULL;
   if (root->key == n1 || root->key == n2)
      return root;
   Node* left_lca = LowestCommonAncestors(root->left, n1, n2);
   Node* right_lca = LowestCommonAncestors(root->right, n1, n2);
   if (left_lca && right_lca)
      return root;
   return (left_lca != NULL) ? left_lca : right_lca;
}
bool printAncestorNodes(struct Node* root, int target){
   if (root == NULL)
      return false;
   if (root->key == target) {
      cout << root->key << "\t";
      return true;
   }
   if (printAncestorNodes(root->left, target) ||
   printAncestorNodes(root->right, target)) {
      cout << root->key << "\t";
      return true;
   }
   return false;
}
bool printcommonAncestors(struct Node* root, int first, int second){
   struct Node* LCA = LowestCommonAncestors(root, first, second);
   if (LCA == NULL)
      return false;
   printAncestorNodes(root, LCA->key);
}
int main(){
   Node* root = insertNode(24);
   root->left = insertNode(8);
   root->right = insertNode(69);
   root->left->left = insertNode(12);
   root->left->right = insertNode(41);
   root->right->left = insertNode(50);
   root->right->right = insertNode(3);
   root->left->left->left = insertNode(22);
   root->right->left->left = insertNode(10);
   root->right->left->right = insertNode(6);
   if (printcommonAncestors(root, 6, 3) == false)
      cout << "No Common nodes";
   return 0;
}

출력 결과

69 24

동작 원리 설명

위 예제에서 노드 6과 노드 3의 최저 공통 조상은 69입니다. LowestCommonAncestors 함수는 재귀적으로 트리를 탐색하여 두 노드가 처음 만나는 지점인 LCA를 찾습니다. 이후 printAncestorNodes 함수는 루트에서 LCA까지 재귀적으로 경로를 추적하며, 경로 위에 있는 노드들을 LCA부터 루트 순으로 출력합니다. 따라서 최종적으로 69와 24가 화면에 출력됩니다.

만약 두 노드 중 하나라도 트리에 존재하지 않아 공통 조상을 찾을 수 없다면, printcommonAncestors 함수가 false를 반환하고 "No Common nodes" 메시지가 출력됩니다. 이 알고리즘의 시간 복잡도는 O(n)으로, 여기서 n은 트리의 전체 노드 수입니다.