Algorithm Guidecomplexity: O(n)

트리 순회 (Tree Traversal)

트리의 모든 노드를 한 번씩 방문하는 방법입니다. 방문 시점에 따라 전위(루트 먼저)·중위(왼쪽→루트→오른쪽, BST에서 정렬 순)·후위(루트 마지막)·레벨 순회로 나뉩니다.

01트리 순회 (Tree Traversal)

알고리즘 작동 원리 탐색

중위 순회(inorder)를 시작합니다. 왼쪽 서브트리 → 루트 → 오른쪽 순서로 방문하며, BST에서는 정렬된 순서로 출력됩니다.

루트 50에서 왼쪽으로, 다시 30의 왼쪽으로 — 가장 왼쪽 20에 도달합니다. 20을 먼저 출력합니다.

20의 왼쪽이 없으니 부모 30을 출력합니다. 출력: 20 · 30

30의 오른쪽 자식 40을 출력합니다. 출력: 20 · 30 · 40

왼쪽 서브트리를 모두 마쳤습니다. 이제 루트 50을 출력합니다. 출력: …40 · 50

오른쪽 서브트리로 이동해 70의 왼쪽 자식 60을 출력합니다. 출력: …50 · 60

60의 부모 70을 출력합니다. 출력: …60 · 70

마지막으로 70의 오른쪽 자식 80을 출력합니다. 출력: …70 · 80

중위 순회 완료 · 20 30 40 50 60 70 80. BST를 중위 순회하면 항상 오름차순 정렬 순서가 됩니다.

Live Python

1def inorder(node):

2 if not node:

3 return

# 왼쪽 먼저

4 inorder(node.left)

5 visit(node) # 왼 → 루트 → 오른

6 inorder(node.right)

1 / 9

02 쉽게 이해하기

For Everyone

🔑핵심 동작

전위·중위·후위는 뿌리를 언제 방문하느냐로 갈립니다. 이진 탐색 트리에서 중위 순회는 값을 오름차순으로 내놓습니다.

💡쉽게 말하면

트리의 모든 노드를 한 번씩 들르는 방법입니다.

루트를 언제 방문하느냐에 따라 전위·중위·후위로 나뉘고, BST를 중위로 돌면 정렬된 순서가 나와요.

📍어디에 쓰나

–폴더 전체 출력
–수식 계산(파스 트리)
–트리 직렬화

03 파이썬 구현 코드

트리 순회 (Tree Traversal)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def inorder(node):
    if not node:
        return
    inorder(node.left)
    visit(node)          # 왼 → 루트 → 오른
    inorder(node.right)

def preorder(node):
    if not node:
        return
    visit(node)          # 루트 먼저
    preorder(node.left)
    preorder(node.right)

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)          # 루트 마지막

04 자주 묻는 질문

FAQ

트리 순회 (Tree Traversal)란 무엇인가요?+

트리 순회 (Tree Traversal)의 시간복잡도는 어떻게 되나요?+

트리 순회 (Tree Traversal)의 시간복잡도는 O(n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

트리 순회 (Tree Traversal)은(는) 어디에 사용하나요?+

폴더 전체 출력, 수식 계산(파스 트리), 트리 직렬화.

트리 순회 (Tree Traversal)를 쉽게 비유하면?+

전위·중위·후위는 뿌리를 언제 방문하느냐로 갈립니다. 이진 탐색 트리에서 중위 순회는 값을 오름차순으로 내놓습니다.

→ 트리 전체 보기Related

🌳AVL 트리 (AVL Tree)

O(log n)

🌳세그먼트 트리 (Segment Tree)

질의·갱신 O(log n)

🌳트라이 (Trie)

O(m) (문자열 길이)