파이썬(Python)으로 구현하는 이진 트리 후위 순회 – 재귀 없이 스택으로 풀기

이진 트리(binary tree)가 하나 있다고 가정해 보겠습니다. 이때 재귀 함수를 사용하지 않고, 오직 반복(iterative) 방식만으로 이 트리의 후위 순회(postorder traversal) 결과를 구해야 합니다.

예를 들어 아래와 같은 트리가 있다고 합시다.

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

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

후위 순회란 무엇인가?

후위 순회는 트리 순회 방식 중 하나로, 각 노드를 왼쪽 자식 → 오른쪽 자식 → 부모(루트) 순서로 방문하는 방법입니다. 즉, 자식 노드들을 모두 처리한 뒤에야 현재 노드를 마지막에 방문하기 때문에 'post(후)' order라는 이름이 붙었습니다.

알고리즘 접근 방법

재귀 호출 대신 스택(stack)을 사용하되, 각 노드를 '(노드, 상태 플래그)' 쌍(pair)으로 관리하는 것이 핵심 아이디어입니다. 플래그 값은 해당 노드를 처음 만났는지(0), 이미 자식 처리를 마치고 값을 기록할 차례인지(1)를 구분해 줍니다.

• 루트(root)가 null이면 빈 배열을 반환합니다.
• 결과를 저장할 배열 res를 생성합니다.
• 스택을 정의하고 [root, 0] 쌍을 넣어 초기화합니다.
• 스택이 비어 있지 않은 동안 다음을 반복합니다.
  • 스택의 최상단(top) 요소를 꺼냈습니다(pop).
  • 꺼낸 쌍의 두 번째 값(플래그)이 0이라면:
    • current := 쌍의 첫 번째 값(노드)
    • (current, 1) 쌍을 스택에 다시 삽입합니다.
    • current의 오른쪽 자식이 존재하면 [오른쪽 자식, 0]을 스택에 삽입합니다.
    • current의 왼쪽 자식이 존재하면 [왼쪽 자식, 0]을 스택에 삽입합니다.
  • 그렇지 않고(플래그가 1이라면) 해당 노드의 데이터를 res에 추가합니다.
• 모든 반복이 끝나면 res를 반환합니다.

동작 원리 이해하기

플래그가 0인 노드를 만나면 일단 자기 자신을 플래그 1로 되돌려 놓고, 오른쪽 자식과 왼쪽 자식을 차례로 스택 위에 올립니다. 스택 특성상 나중에 넣은 왼쪽 자식이 먼저 처리되므로, 결과적으로 왼쪽 → 오른쪽 → 부모 순서로 값이 기록됩니다. 이것이 바로 후위 순회의 방문 순서와 일치합니다.

구현 예제 코드

아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.

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]

마무리

이처럼 스택과 상태 플래그를 조합하면 재귀 호출 없이도 후위 순회를 깔끔하게 구현할 수 있습니다. 이 방법은 재귀의 깊이 제한(recursion limit)을 걱정할 필요가 없어, 매우 깊은 트리를 다룰 때 특히 유용합니다. 전위 순회(preorder)나 중위 순회(inorder)도 같은 패턴을 응용해 구현할 수 있으니 함께 연습해 보시길 추천합니다.