레벨 순회 (Level-order Traversal, BFS) 개념 이진 트리를 위에서 아래로, 같은 레벨에서는 왼쪽 → 오른쪽 순서로 방문 너비 우선 탐색(BFS)을 트리에 적용한 형태 재귀로 구현되는 다른 순회(inorder/preorder/postorder)와 달리 큐(Queue)로 구현 동작 원리 루트를 큐에 넣는다 (offer) 큐가 빌 때까지 반복: 큐에서 하나 꺼내(poll) 방문 그 노드의 왼쪽 자식 → 오른쪽 자식 순으로 큐에 넣는다 먼저 들어간 노드가 먼저 나오는 FIFO 성질 덕분에 레벨 순서가 유지됨 시간 복잡도 항목 복잡도 시간 O(n) 공간 O(n) 시간: 모든 노드를 정확히 한 번씩 방문 공간: 최악의 경우 한 레벨의 노드가 모두 큐에 들어감 (가장 넓은 레벨 = 최대 n/2개) Successor / Predecessor (BST) 개념 Successor: key[x]보다 크면서 가장 작은 키를 가진 노드 Predecessor: key[x]보다 작으면서 가장 큰 키를 가진 노드 서로 좌우 대칭 관계 (모든 키는 서로 다르다고 가정) 구현 시 각 노드에 부모 포인터(parent) 가 필요 동작 원리 (Successor) 오른쪽 부트리가 있는 경우 → 오른쪽 부트리의 최솟값 오른쪽 부트리가 없는 경우 → 부모를 따라 올라가면서 처음으로 왼쪽 자식이 되는 노드의 부모 그런 노드가 없는 경우 → null (x가 트리의 최댓값) 동작 원리 (Predecessor) Successor에서 좌우만 반전 왼쪽 부트리가 있는 경우 → 왼쪽 부트리의 최댓값 왼쪽 부트리가 없는 경우 → 부모를 따라 올라가면서 처음으로 오른쪽 자식이 되는 노드의 부모 그런 노드가 없는 경우 → null (x가 트리의 최솟값) 시간 복잡도 항목 복잡도 시간 O(h) 공간 O(1) h는 트리의 높이 (균형 트리면 O(log n), 최악의 경우 O(n))