[Binary Search Tree] Lowest Common Ancestor

난이도: ★★☆☆☆ • solved on: 2025-12-07

---

문제 요약

• 문제 유형: BST, 트리 탐색, 재귀
• 요구사항: BST에서 두 값 v1, v2의 LCA(Lowest Common Ancestor) 를 찾아 반환해야 한다.

---

사용 개념

1. 자료구조

   • Binary Search Tree
   • Node 구조(data, left, right)

2. 알고리즘/기법

   • BST 특성 기반 분기 탐색
   • 재귀 호출(recursion)

3. 핵심 키워드

   • LCA
   • BST property (왼쪽 < root < 오른쪽)

---

풀이 아이디어

1. 문제 분해

• v1, v2 중 더 큰 값과 작은 값을 먼저 정한다.
• root.data < 작은 값 → 두 값 모두 오른쪽에 있으므로 오른쪽으로 이동
• root.data > 큰 값 → 두 값 모두 왼쪽에 있으므로 왼쪽으로 이동
• 그 외의 경우는 값들이 양쪽에 걸쳐 있으므로 현재 root가 LCA가 된다.

2. 핵심 로직 흐름

   if (root < min) → 오른쪽
   if (root > max) → 왼쪽
   else → root가 LCA

3. 예외 처리

   • root == null인 입력은 문제 조건상 발생하지 않는다.
   • v1 == v2도 동일 로직으로 root까지 자연스럽게 찾아간다.

---

코드

public static Node lca(Node root, int v1, int v2) {
    int max = Math.max(v1, v2);
    int min = Math.min(v1, v2);

    if (root.data < min) {
        return lca(root.right, v1, v2);
    }
    if (root.data > max) {
        return lca(root.left, v1, v2);
    }
    return root;
}

---

시간·공간 복잡도

• 시간 복잡도: O(H) (H = 트리 높이, 평균은 logN, 최악은 N)
• 공간 복잡도: O(H) (재귀 스택 크기)

---

어려웠던 점

• 분기 방향을 어떻게 잡을지 고민이 있었다. 처음에는 단순히 오른쪽으로만 이동하도록 구현했으나, BST에서는 두 값이 root 기준으로 어느 방향에 위치하는지 판단해야 한다는 점을 뒤늦게 파악하여 정리했다.
• 특히, 값들이 서로 다른 방향에 존재하는 지점이 LCA라는 핵심 개념을 파악하면서 로직이 단순해졌다.

---

배운 점 및 팁

• BST에서의 LCA는 일반 트리보다 훨씬 명확하다. “왼쪽인가? 오른쪽인가? 아니면 양쪽인가?” 이 세 가지 분기만 이해하면 항상 풀 수 있다.
• v1, v2의 순서를 정리한 뒤 max/min 기준으로 비교하면 조건문이 깔끔해진다.

---

참고 및 링크

• 문제 링크: https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem
• 참고 블로그/깃허브: https://en.wikipedia.org/wiki/Lowest_common_ancestor

---

추가 연습 문제

• 비슷한 유형 (GPT 추천)

  • Binary Search Tree : Insertion
  • Binary Search Tree : Height

• 확장 문제 (GPT 추천)

  • Baekjoon 11437 LCA
  • Baekjoon 3584 가장 가까운 공통 조상