[DSA][Trees] 07. Lowest Common Ancestor of a Binary Search Tree

LeetCode 235

 

07. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia:
“The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

 

[질문하기]

- 트리의 노드에 중복되는 값이 있을 수 있나요?

- 두 노드가 트리에 항상 존재한다고 가정해도 되나요?

 

[아이디어]

- 현재 노드의 값이 두 노드의 값 사이에 있을 때, 이 노드가 LCA이다.

 

 

[풀이 1] Binary Search Tree

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        pVal, qVal = p.val, q.val
        if pVal > qVal:
            pVal, qVal = qVal, pVal
        
        while True:
            if pVal <= root.val <= qVal:
                return root
            elif qVal < root.val:
                root = root.left
            elif pVal > root.val:
                root = root.right

이 문제에서 중요한 포인트는 주어진 트리가 '이진 탐색 트리(BST)'라는 것이다.

BST는 왼쪽 서브트리에 더 작은 값들이, 오른쪽 서브트리에 더 큰 값들이 오는 특성을 가지고 있다. 이 특성을 이용하면, 두 노드의 공통 조상(LCA)은 왼쪽과 오른쪽으로 갈라지기 전 가장 마지막 노드라는 점을 활용해 구할 수 있다.

• 현재 노드의 값이 두 노드 p와 q의 값보다 크면, 두 노드는 현재 노드의 왼쪽 서브트리에 있으므로 왼쪽으로 이동한다.
• 반대로, 현재 노드의 값이 두 노드 p와 q의 값보다 작으면, 두 노드는 현재 노드의 오른쪽 서브트리에 있으므로 오른쪽으로 이동한다.
• 만약 현재 노드의 값이 두 노드 p와 q보다 크거나 작고, 두 노드가 각각 왼쪽과 오른쪽에 위치한다면, 현재 노드를 기점으로 두 노드가 갈라지게 되므로, 현재 노드가 두 노드의 공통 조상(LCA)이다.

 

⏱️ 시간복잡도

트리의 높이만큼 순회하므로 시간 복잡도는 O(h)이다.

즉, 평균적으로는 O(logn), 최악의 경우 O(n)의 시간 복잡도를 가진다.

🧠 공간복잡도

반복문을 사용하여 추가 공간을 사용하지 않으므로 O(1)의 공간 복잡도를 가진다.