파이썬으로 배우는 이진 트리 후위 순회 — 스택을 활용한 반복적 구현

후위 순회(Postorder Traversal)는 이진 트리 순회 방식 중 하나로, 각 노드를 왼쪽 자식 → 오른쪽 자식 → 루트 순서로 방문합니다. 이 글에서는 재귀 함수 없이 스택(Stack)만을 이용해 후위 순회를 반복적(iterative)으로 구현하는 방법을 살펴보겠습니다.

예를 들어 다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.

이 트리의 후위 순회 결과는 다음과 같습니다.

[9, 15, 7, 10, -10]

알고리즘 접근 방법

재귀 호출은 함수 호출 오버헤드가 있고, 트리의 깊이가 매우 깊은 경우 스택 오버플로우가 발생할 수 있습니다. 이를 피하기 위해 각 노드를 (노드, 상태) 형태의 쌍(pair)으로 스택에 저장하는 방식을 사용합니다. 상태 값의 의미는 다음과 같습니다.

상태 0: 아직 자식 노드를 처리하지 않은 상태
상태 1: 자식 노드 처리가 끝나 자신의 값을 출력할 차례인 상태

전체 알고리즘은 다음과 같이 진행됩니다.

루트가 null이면 빈 배열을 반환합니다.
결과를 담을 배열 res를 생성합니다.
스택에 [root, 0] 쌍을 넣습니다.
스택이 빌 때까지 다음을 반복합니다.
- 스택의 최상단 요소를 꺼냅니다.
- 꺼낸 요소의 상태 값이 0이라면:
  - current를 해당 노드로 설정합니다.
  - [current, 1]을 스택에 다시 삽입합니다.
  - 오른쪽 자식이 존재하면 [오른쪽 자식, 0]을 스택에 삽입합니다.
  - 왼쪽 자식이 존재하면 [왼쪽 자식, 0]을 스택에 삽입합니다.
- 상태 값이 0이 아니라면(즉, 1이라면) 해당 노드의 데이터를 res에 추가합니다.
res를 반환합니다.

참고: 스택은 LIFO(Last-In-First-Out) 구조이므로, 왼쪽 자식을 먼저 처리하려면 오른쪽 자식을 먼저 스택에 넣어야 합니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — 모든 노드를 정확히 두 번씩 방문합니다.
공간 복잡도: O(n) — 최악의 경우 스택에 트리의 모든 노드가 저장될 수 있습니다.

Python 구현 예제

다음은 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.

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


def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)


def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree


class Solution(object):
    def postorderTraversal(self, root):
        if not root:
            return []
        res = []
        stack = [[root, 0]]
        while stack:
            node = stack[-1]
            stack.pop()
            if node[1] == 0:
                current = node[0]
                stack.append([current, 1])
                if current.right:
                    stack.append([current.right, 0])
                if current.left:
                    stack.append([current.left, 0])
            else:
                if node[0].data != 0:
                    res.append(node[0].data)
        return res


ob = Solution()
root = make_tree([-10, 9, 10, None, None, 15, 7])
print(ob.postorderTraversal(root))

입력

[-10,9,10,None,None,15,7]

출력

[9, 15, 7, 10, -10]

마무리

이처럼 (노드, 상태) 쌍을 활용한 스택 기반 접근법을 사용하면 재귀 없이도 이진 트리의 후위 순회를 안전하고 효율적으로 구현할 수 있습니다. 같은 원리를 응용하면 전위 순회(preorder)나 중위 순회(inorder)의 반복적 구현에도 쉽게 적용할 수 있으니, 직접 코드를 변형해 보면서 개념을 익혀 보시기 바랍니다.