이진 트리 레벨 순회 (Binary Tree Level Order Traversal)

이진 트리 레벨 순회는

이진 트리의 낮은 레벨의 노드부터 순차적으로 방문합니다.

트리를 너비우선탐색(BFS(Breadth first search)) 하는 것 입니다.

이진 트리 레벨 순회

위 그림에서,

Level1 - 1

Level2 - 2, 3

Level3 - 4, 5, 6, 7

 

즉, 1->2->3->4->5->6->7 이렇게 방문합니다.

 

 

1 2 4 5 3 6 7

 

구현 (큐 자료구조)

큐 자료구조를 사용해서 재귀적 방법의 시간 복잡도를 O(n)으로 줄일 수 있습니다.

 

시간 복잡도 : O(n)

공간 복잡도 : O(n)

 

소스 코드

from collections import deque


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def print_level_order(root):
    if root is None:
        return

    # 덱 생성 후 root 노드 추가
    q = deque()
    q.append(root)

    level = 0

    while q:
        values = []

        # 현재 시점에 q에는 같은 레벨의 노드가 들어가 있음
        for _ in range(len(q)):
            node = q.popleft()
            if node:
                values.append(node.val)
                q.append(node.left)
                q.append(node.right)

        # 출력
        if values:
            print(f'level : {level}, values : {values}')

        level += 1


# 7개의 노드 생성
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)

# node1을 root로 지정
root = node1

# 이진 트리 구성
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

# 이진 트리 레벨 순회
print_level_order(root)

출력

level : 0, values : [1]
level : 1, values : [2, 3]
level : 2, values : [4, 5, 6, 7]

 

참고:

https://www.geeksforgeeks.org/level-order-tree-traversal/

https://www.techiedelight.com/level-order-traversal-binary-tree/