Lowest Common Ancestor of a Binary Search Tree

문제

이진 탐색 트리(BST)의 루트 노드와 트리 내의 두 노드 p, q가 주어질 때, 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 프로그램을 작성하는 문제입니다. 최소 공통 조상이란, 트리 내의 어떤 노드 T가 p와 q를 모두 자손으로 가지면서 가장 깊은(낮은) 위치에 있는 노드를 의미합니다. (노드 자기 자신도 자손으로 간주합니다.)

• 입력: 이진 탐색 트리의 루트 노드 root, 탐색 대상 노드 p, q
• 출력: 두 노드의 최소 공통 조상 노드를 반환합니다.

링크: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree

풀이: 이진 탐색 트리(BST)의 대소 관계 속성 활용

이진 탐색 트리는 "왼쪽 서브트리의 모든 노드는 부모 노드보다 작고, 오른쪽 서브트리의 모든 노드는 부모 노드보다 크다"는 강력한 특징을 가지고 있습니다. 이 특징을 활용하면 트리를 전부 탐색하지 않고도 최소 공통 조상을 단번에 찾아낼 수 있습니다.

• 기저 조건: 탐색 중인 노드(root)가 null이라면 더 이상 탐색할 수 없으므로 null을 반환합니다.
• 공통 조상 판별 (분기점 확인):
  • 현재 노드(root.val)의 값이 p.val과 q.val의 사이에 있다면 (하나는 작거나 같고, 다른 하나는 크거나 같다면), 현재 노드가 두 노드가 갈라지는 분기점이 됩니다. 즉, 이 노드가 바로 최소 공통 조상(LCA)입니다.
• 오른쪽 서브트리 탐색:
  • 만약 공통 조상 판별 조건에 해당하지 않으면서 root.val < p.val이라면, (앞선 조건이 거짓이므로 root.val < q.val 역시 참이 됩니다) p와 q 두 노드 모두 현재 노드보다 큽니다. 따라서 공통 조상은 무조건 오른쪽 서브트리에 존재하므로 오른쪽으로 재귀 호출을 수행합니다.
• 왼쪽 서브트리 탐색:
  • 반대로 두 노드가 모두 현재 노드보다 작다면 공통 조상은 왼쪽 서브트리에 존재하므로 왼쪽으로 재귀 호출을 수행합니다.

코드

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 1. 기저 조건
        if (root == null) {
            return null;
        }

        // 2. 현재 노드의 값이 p와 q의 사이에 있다면 현재 노드가 최소 공통 조상
        if (root.val <= p.val && root.val >= q.val || root.val <= q.val && root.val >= p.val) {
            return root;
        } 
        // 3. 현재 노드의 값이 p보다 작다면 (즉, p와 q 모두 root보다 크다면) 오른쪽 탐색
        else if (root.val < p.val) {
            return lowestCommonAncestor(root.right, p, q);
        } 
        // 4. 현재 노드의 값이 p, q보다 크다면 왼쪽 탐색
        else {
            return lowestCommonAncestor(root.left, p, q);
        }
    }
}

알고리즘 분류

자료 구조 (Data Structures), 트리 (Tree), 이진 탐색 트리 (Binary Search Tree), 깊이 우선 탐색 (DFS), 재귀 (Recursion)