이진 트리 반시계 방향 나선형 순회 알고리즘 구현하기

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 하나의 이진 트리가 주어졌을 때, 이 트리를 반시계 방향(anti-clockwise) 나선형으로 순회하는 것입니다.

순회 과정은 아래 그림과 같습니다.

위 트리를 반시계 방향으로 순회하면 다음과 같은 순서로 노드를 방문하게 됩니다.

순회 결과: 1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7

알고리즘 개념

핵심 아이디어는 간단합니다. 트리의 최상위 레벨(1)부터 최하위 레벨(트리의 높이)까지 두 개의 포인터 i와 j를 사용하여 양쪽 끝에서 안쪽으로 이동하면서 레벨을 처리하는 것입니다.

flag가 false일 때: 위쪽 레벨(i)의 노드들을 오른쪽에서 왼쪽 방향으로 출력한 후, i를 1 증가시킵니다.
flag가 true일 때: 아래쪽 레벨(j)의 노드들을 왼쪽에서 오른쪽 방향으로 출력한 후, j를 1 감소시킵니다.

이렇게 방향을 번갈아 전환하면 나선형으로 회전하듯이 트리를 순회할 수 있습니다.

의사 코드 (Pseudocode)

antiClockTraverse(root)

Begin
    i := 1, j := height of the tree
    flag := false
    while i <= j, do
        if flag is false, then
            print tree elements from right to left for level i
            flag := true
            i := i + 1
        else
            print tree elements from left to right for level j
            flag := false
            j := j - 1
        end if
    done
End

C++ 구현 예제

#include<iostream>
using namespace std;
class Node {
    public:
        Node* left;
        Node* right;
        int data;
    Node(int data) { //노드 생성자
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int getHeight(Node* root) {
    if (root == NULL)
    return 0;
    //왼쪽과 오른쪽 서브트리의 높이 계산
    int hl = getHeight(root->left);
    int hr = getHeight(root->right);
    return 1 + max(hl, hr); //루트 포함하여 1 추가
}
void printLeftToRight(class Node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        printLeftToRight(root->left, level - 1);
        printLeftToRight(root->right, level - 1);
    }
}
void printRightToLeft(struct Node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        printRightToLeft(root->right, level - 1);
        printRightToLeft(root->left, level - 1);
    }
}
void antiClockTraverse(class Node* root) {
    int i = 1;
    int j = getHeight(root);
    int flag = 0; //방향 전환에 사용되는 플래그
    while (i <= j) {
        if (flag == 0) {
            printRightToLeft(root, i);
            flag = 1; //왼쪽에서 오른쪽 출력으로 전환
            i++;
        }else {
            printLeftToRight(root, j);
            flag = 0; //오른쪽에서 왼쪽 출력으로 전환
            j--;
        }
    }
}
int main() {
    struct Node* root;
    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(8);
    root->left->left->right = new Node(9);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(11);
    root->right->left->left = new Node(12);
    root->right->left->right = new Node(13);
    root->right->right->left = new Node(14);
    root->right->right->right = new Node(15);
    antiClockTraverse(root);
}

실행 결과

1 8 9 10 11 12 13 14 15 3 2 4 5 6 7

동작 원리 정리

예제 트리는 총 4개의 레벨로 구성되어 있습니다. 알고리즘의 동작 순서를 단계별로 살펴보면 다음과 같습니다.

레벨 1 (오른쪽 → 왼쪽): 루트 노드 1을 출력합니다.
레벨 4 (왼쪽 → 오른쪽): 가장 아래 레벨의 노드들 8, 9, 10, 11, 12, 13, 14, 15를 출력합니다.
레벨 2 (오른쪽 → 왼쪽): 노드 3, 2를 출력합니다.
레벨 3 (왼쪽 → 오른쪽): 노드 4, 5, 6, 7을 출력합니다.

이처럼 위와 아래 레벨을 교차하며 방향을 바꿔가며 순회하기 때문에 마치 나선이 반시계 방향으로 감기는 듯한 순회 순서를 얻을 수 있습니다.

시간 복잡도

각 레벨마다 재귀적으로 트리를 탐색하므로 시간 복잡도는 O(n²)입니다. 여기서 n은 트리의 노드 수입니다. 각 레벨 출력 함수가 해당 레벨까지의 경로를 따라 내려가기 때문에 비효율적일 수 있으며, 큐(Queue)를 활용하면 O(n)으로 최적화할 수 있습니다.