파이썬(Python)으로 부모 포인터를 활용해 이진 트리의 최소 공통 조상(LCA) 찾기

문제 소개

이진 트리와 두 개의 특정 노드 x, y가 주어졌다고 가정해 보겠습니다. 이때 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾아 반환해야 합니다. 이진 트리에서 최소 공통 조상이란 노드 x와 y가 모두 그 노드의 자손(descendant)이 되는 가장 낮은 위치의 노드를 의미하며, 한 노드는 자기 자신의 자손이 될 수도 있습니다.

노드 구조

이 문제의 트리 노드는 일반적인 이진 트리 노드에 parent(부모) 포인터가 추가된 구조입니다.

TreeNode:
    data:   <정수>
    left:   <TreeNode 포인터>
    right:  <TreeNode 포인터>
    parent: <TreeNode 포인터>

풀이 과정에서 반드시 이 부모 포인터를 활용해야 한다는 점이 핵심입니다.

예시

예를 들어 다음과 같은 이진 트리가 있고 x = 3, y = 7이라고 해보겠습니다.

노드 3과 노드 7은 모두 노드 5의 자손이므로, 최소 공통 조상은 5이며 출력값 역시 5가 됩니다.

풀이 접근 방법

부모 포인터가 있다면 어떤 노드든 루트까지의 경로를 손쉽게 구할 수 있습니다. 이 성질을 이용해 다음 단계로 문제를 해결합니다.

1. path_p_r이라는 새로운 리스트를 생성합니다.

2. x가 null이 아닌 동안 다음을 반복합니다.

   • x를 path_p_r의 끝에 추가합니다.

   • x를 x의 부모 노드로 갱신합니다.

3. y가 null이 아닌 동안 다음을 반복합니다.

   • y가 path_p_r에 존재하면 y를 반환합니다. 두 경로가 처음 만나는 지점, 즉 LCA입니다.

   • y를 y의 부모 노드로 갱신합니다.

요약하면, x부터 루트까지의 조상 목록을 미리 만들어 두고, y를 루트 방향으로 한 칸씩 올려가며 목록에 처음 등장하는 노드를 찾으면 그것이 바로 최소 공통 조상입니다.

구현 예제

class TreeNode:
   def __init__(self, data, left=None, right=None, parent=None):
      self.data = data
      self.left = left
      self.right = right
      self.parent = parent

def insert(temp, data):
   que = []
   que.append(temp)
   while len(que):
      temp = que.pop(0)
      if not temp.left:
         if data is not None:
            temp.left = TreeNode(data, parent=temp)
         else:
            temp.left = TreeNode(0, parent=temp)
         break
      else:
         que.append(temp.left)
      if not temp.right:
         if data is not None:
            temp.right = TreeNode(data, parent=temp)
         else:
            temp.right = TreeNode(0, parent=temp)
         break
      else:
         que.append(temp.right)

def make_tree(elements):
   tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(tree, element)
   return tree

def search_node(root, element):
   if root is None:
      return None
   if root.data == element:
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2

def solve(x, y):
   path_p_r = []
   while x:
      path_p_r.append(x)
      x = x.parent
   while y:
      if y in path_p_r:
         return y
      y = y.parent

root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(search_node(root, 3), search_node(root, 7)).data)

실행 결과

입력

[5, 3, 7, 2, 4, 1, 7, 6, 8, 10], x = 3, y = 7

출력

5

복잡도 분석

시간 복잡도: 첫 번째 반복문은 x에서 루트까지, 두 번째 반복문은 y에서 루트까지 순회하므로 트리의 높이 h에 비례합니다. 다만 리스트의 멤버십 검사(in)가 선형 탐색이므로 최악의 경우 O(h²)까지 늘어날 수 있습니다. 조상 목록을 집합(set)으로 관리하면 평균 O(1) 조회가 가능해져 전체를 O(h)로 개선할 수 있습니다.

공간 복잡도: x의 조상 경로를 저장해야 하므로 O(h)의 추가 공간이 필요합니다.