파이썬으로 이진 트리의 유일한 자식 노드 개수 구하기 – BFS 알고리즘 예제

문제 개요

이진 트리가 하나 주어졌을 때, '유일한 자식(only child)'에 해당하는 노드의 개수를 구하는 것이 목표입니다. 여기서 어떤 노드 x가 유일한 자식 노드라는 것은, 그 부모 노드가 정확히 하나의 자식, 즉 x만을 가지고 있는 경우를 의미합니다.

예를 들어 다음과 같은 트리가 입력으로 주어진다면:

출력은 2가 됩니다. 값이 8인 노드와 값이 6인 노드가 각각 부모 입장에서 유일한 자식이기 때문입니다.

풀이 접근 방법

이 문제는 너비 우선 탐색(BFS)을 활용하면 직관적으로 해결할 수 있습니다. 큐(데크)를 사용해 트리를 레벨 순서대로 순회하면서, 각 노드를 방문할 때마다 자식의 상태를 확인하고 한쪽 자식만 존재하는 경우 카운트를 1씩 증가시킵니다.

구체적인 알고리즘은 다음과 같습니다.

1. 루트가 null이면 0을 반환합니다.
2. 양방향 큐(deque)를 생성합니다.
3. 큐의 맨 뒤에 루트를 삽입합니다.
4. 카운트 변수(count)를 0으로 초기화합니다.
5. 큐가 빌 때까지 아래 과정을 반복합니다.
   • 큐의 앞에서 요소를 꺼내 current로 지정합니다.
   • current의 왼쪽 자식이 존재하면 큐에 추가하고, 이때 오른쪽 자식이 없다면 count를 1 증가시킵니다.
   • current의 오른쪽 자식이 존재하면 큐에 추가하고, 이때 왼쪽 자식이 없다면 count를 1 증가시킵니다.
6. 순회가 끝나면 count를 반환합니다.

예제 코드

아래는 위 알고리즘을 파이썬으로 구현한 코드입니다. 좌우 자식 검사를 서로 독립적으로 처리하도록 작성하여, 오른쪽 자식만 있는 노드의 하위 트리도 누락 없이 탐색할 수 있습니다.

from collections import deque

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

class Solution:
   def solve(self, root):
       if not root:
           return 0
       d = deque([root])
       count = 0
       while d:
           current = d.popleft()
           if current.left:
               d.append(current.left)
               if not current.right:
                   count += 1
           if current.right:
               d.append(current.right)
               if not current.left:
                   count += 1
       return count

ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)
print(ob.solve(root))

실행 결과

위 코드에서 구성한 트리는 루트 9를 중심으로 왼쪽에 7, 오른쪽에 10이 있으며, 7의 오른쪽 자식으로 8, 10의 오른쪽 자식으로 6이 연결되어 있습니다.

2

노드 7은 오직 8만, 노드 10은 오직 6만 자식으로 가지므로, 유일한 자식 노드는 총 2개입니다.

정리

BFS 기반 순회를 사용하면 시간 복잡도 O(n), 공간 복잡도 O(n)으로 트리의 모든 노드를 한 번씩만 방문하며 문제를 해결할 수 있습니다. 재귀적 풀이(DFS)보다 깊은 트리에서 스택 오버플로우 걱정이 없다는 장점도 있습니다.