이진 트리가 하나 주어졌을 때, 루트 노드부터 시작하는 중위 순회(Inorder Traversal) 결과를 리스트 형태로 반환하는 프로그램을 만들어 보겠습니다.
중위 순회는 트리의 모든 노드를 다음과 같은 순서로 방문하는 순회 방식입니다.
왼쪽 서브트리를 먼저 재귀적으로 순회합니다.
현재 노드를 방문(처리)합니다.
오른쪽 서브트리를 재귀적으로 순회합니다.
일반적으로 중위 순회는 재귀 호출로 쉽게 구현할 수 있지만, 이번 글에서는 재귀 없이 스택을 활용한 반복(iterative) 방식으로 문제를 해결해 보겠습니다.
문제 예시
예를 들어 아래와 같은 이진 트리가 입력으로 주어진다고 가정해 봅시다.
이 트리에 대해 중위 순회를 수행하면 출력 결과는 다음과 같습니다.
[12, 13, 4, 16, 7, 14, 22]
알고리즘 접근 방법
반복 방식으로 중위 순회를 구현하려면 명시적인 스택을 사용하여 재귀 호출의 동작을 흉내 내야 합니다. 해결 과정은 다음과 같습니다.
inorder: 결과를 저장할 새로운 리스트를 생성합니다.stack: 노드를 임시로 보관할 빈 스택을 준비합니다.다음 과정을 무한히 반복합니다.
현재
root가 null이 아니라면 → 해당 노드를 스택에 push하고,root를 왼쪽 자식 노드로 이동합니다.그렇지 않고 스택이 비어 있지 않다면 → 스택에서 노드를 pop하여
root로 설정하고, 그 값을inorder리스트 끝에 추가한 뒤,root를 오른쪽 자식 노드로 이동합니다.그 외의 경우(root가 null이고 스택도 비어 있음) → 모든 노드를 방문했으므로 반복문을 종료합니다.
완성된
inorder리스트를 반환합니다.
이 알고리즘의 시간 복잡도는 각 노드를 정확히 한 번씩 방문하므로 O(n)이며, 공간 복잡도는 스택 깊이에 따라 최악의 경우 O(n)입니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
class Solution:
def solve(self, root):
inorder = []
stack = []
while True:
if root:
stack.append(root)
root = root.left
elif stack:
root = stack.pop()
inorder.append(root.val)
root = root.right
else:
break
return inorder
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))입력
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
출력
[12, 13, 4, 16, 7, 14, 22]
동작 원리 정리
이 알고리즘의 핵심은 두 가지 상태를 번갈아 처리하는 것입니다. 첫째, 아직 방문하지 않은 노드가 남아 있다면 계속 왼쪽으로 내려가면서 경로상의 노드를 스택에 쌓습니다. 둘째, 더 이상 왼쪽으로 갈 수 없으면 스택에서 노드를 꺼내 값을 기록하고 오른쪽 서브트리로 이동합니다. 이 과정을 통해 재귀 함수 없이도 중위 순회의 '왼쪽 → 루트 → 오른쪽' 순서를 정확하게 유지할 수 있습니다.