README.md

레벨 순회 (Level-order Traversal, BFS)

개념

• 이진 트리를 위에서 아래로, 같은 레벨에서는 왼쪽 → 오른쪽 순서로 방문
• 너비 우선 탐색(BFS)을 트리에 적용한 형태
• 재귀로 구현되는 다른 순회(inorder/preorder/postorder)와 달리 큐(Queue)로 구현

동작 원리

1. 루트를 큐에 넣는다 (offer)
2. 큐가 빌 때까지 반복:
   • 큐에서 하나 꺼내(poll) 방문
   • 그 노드의 왼쪽 자식 → 오른쪽 자식 순으로 큐에 넣는다

• 먼저 들어간 노드가 먼저 나오는 FIFO 성질 덕분에 레벨 순서가 유지됨

시간 복잡도

항목	복잡도
시간	O(n)
공간	O(n)

• 시간: 모든 노드를 정확히 한 번씩 방문
• 공간: 최악의 경우 한 레벨의 노드가 모두 큐에 들어감 (가장 넓은 레벨 = 최대 n/2개)

Successor / Predecessor (BST)

개념

• Successor: key[x]보다 크면서 가장 작은 키를 가진 노드
• Predecessor: key[x]보다 작으면서 가장 큰 키를 가진 노드
• 서로 좌우 대칭 관계 (모든 키는 서로 다르다고 가정)
• 구현 시 각 노드에 부모 포인터(parent) 가 필요

동작 원리 (Successor)

1. 오른쪽 부트리가 있는 경우 → 오른쪽 부트리의 최솟값
2. 오른쪽 부트리가 없는 경우 → 부모를 따라 올라가면서 처음으로 왼쪽 자식이 되는 노드의 부모
3. 그런 노드가 없는 경우 → null (x가 트리의 최댓값)

동작 원리 (Predecessor)

• Successor에서 좌우만 반전

1. 왼쪽 부트리가 있는 경우 → 왼쪽 부트리의 최댓값
2. 왼쪽 부트리가 없는 경우 → 부모를 따라 올라가면서 처음으로 오른쪽 자식이 되는 노드의 부모
3. 그런 노드가 없는 경우 → null (x가 트리의 최솟값)

시간 복잡도

항목	복잡도
시간	O(h)
공간	O(1)

• h는 트리의 높이 (균형 트리면 O(log n), 최악의 경우 O(n))