Python으로 이진 탐색 트리에서 노드의 형제 값 찾기

문제 개요

값 k와 이진 탐색 트리(Binary Search Tree)가 하나씩 주어져 있다고 가정해 봅시다. 이 트리의 각 노드는 리프 노드이거나 정확히 두 개의 자식 노드를 가지고 있습니다. 목표는 값 k를 가진 노드를 찾아, 그 노드의 형제(sibling) 노드의 값을 반환하는 것입니다.

예를 들어 위 트리에서 k = 4라면, 4의 형제 노드는 10이므로 출력 결과는 10입니다.

풀이 접근 방법

이 문제는 이진 탐색 트리의 정렬된 성질을 활용해 재귀적으로 해결할 수 있습니다. 핵심 아이디어는 k를 가진 노드를 향해 트리를 내려가되, 해당 노드의 부모 입장에서 형제 노드의 값을 기록하는 것입니다.

util() 함수 로직

루트의 왼쪽 자식과 오른쪽 자식이 모두 None이면(리프 노드에 도달하면) 그대로 종료합니다.
k가 루트의 값보다 큰 경우:
- 오른쪽 자식의 값이 k와 같다면, 형제인 왼쪽 자식의 값을 ans에 추가하고 종료합니다.
- 그렇지 않으면 오른쪽 서브트리에 대해 util()을 재귀 호출합니다.
k가 루트의 값보다 작은 경우:
- 왼쪽 자식의 값이 k와 같다면, 형제인 오른쪽 자식의 값을 ans에 추가하고 종료합니다.
- 그렇지 않으면 왼쪽 서브트리에 대해 util()을 재귀 호출합니다.

메인 실행 흐름

결과를 담을 빈 리스트 ans를 생성합니다.
util(root, k, ans)를 호출해 트리를 탐색합니다.
ans[0]을 반환합니다.

시간 복잡도는 트리의 높이에 비례하여 O(h)입니다. 균형 잡힌 이진 탐색 트리라면 O(log n)으로 매우 효율적으로 동작합니다.

구현 예제

다음 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.

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

def util(root, k, ans):
    if root.left is None and root.right is None:
        return
    if k > root.val:
        if root.right.val == k:
            ans.append(root.left.val)
            return
        else:
            util(root.right, k, ans)
    if k < root.val:
        if root.left.val == k:
            ans.append(root.right.val)
            return
        else:
            util(root.left, k, ans)

class Solution:
    def solve(self, root, k):
        ans = []
        util(root, k, ans)
        return ans[0]

root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
ob1 = Solution()
print(ob1.solve(root, 4))

입력

root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
4