C++에서 재귀와 스택 없이 이진 트리 후위 순회 구현하기

문제 소개

이번 문제에서는 하나의 이진 트리가 주어지며, 재귀(recursion)와 스택(stack)을 사용하지 않고 이진 트리의 후위 순회 결과를 출력하는 것이 목표입니다.

이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 특수한 형태의 트리 자료구조입니다.

후위 순회(Postorder Traversal)란?

후위 순회는 대표적인 트리 순회 기법 중 하나로, 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서로 노드를 방문합니다. 즉, 자식 노드들을 모두 먼저 처리한 뒤에 부모(루트) 노드를 가장 마지막에 방문하는 방식입니다.

위 트리의 후위 순회 결과는 다음과 같습니다.

8 → 4 → 2 → 7 → 9 → 6

접근 방법

재귀 호출이나 스택 없이 트리를 순회하려면 깊이 우선 탐색(DFS)에 기반한 반복(iterative) 기법을 활용하고, 방문한 노드의 정보는 해시 테이블(hash table)에 저장하는 방식으로 문제를 해결할 수 있습니다.

예제 코드 1 — unordered_set 활용

다음은 위 접근 방식을 구현한 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};

void postOrderTraversal(struct Node* head) {
    struct Node* temp = head;
    unordered_set<Node*> visited;
    while (temp && visited.find(temp) == visited.end()) {
        if (temp->left && visited.find(temp->left) == visited.end())
            temp = temp->left;
        else if (temp->right && visited.find(temp->right) == visited.end())
            temp = temp->right;
        else {
            cout<<temp->data<<"\t";
            visited.insert(temp);
            temp = head;
        }
    }
}

struct Node* insertNode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}

int main() {
    struct Node* root = insertNode(6);
    root->left = insertNode(2);
    root->right = insertNode(9);
    root->left->left = insertNode(8);
    root->left->right = insertNode(4);
    root->right->left = insertNode(7);
    root->right->left->left = insertNode(13);
    cout<<"Post Order Traversal of the binary tree :\n";
    postOrderTraversal(root);
    return 0;
}

출력 결과

Post Order Traversal of the binary tree :
8    4    2    13    7    9    6

개선된 접근 방법 — unordered_map 활용

첫 번째 방법은 노드 하나를 출력할 때마다 항상 루트(head)부터 다시 탐색을 시작해야 하므로 비효율적입니다. 이를 개선하려면 unordered_map을 사용해 각 노드의 부모 노드를 함께 저장하면 됩니다. 그러면 자식 노드를 모두 방문한 노드는 맵에 기록된 부모 포인터를 참조하여 곧바로 상위 노드로 되돌아갈 수 있으므로, 루트까지 반복해서 거슬러 올라가는 오버헤드를 크게 줄일 수 있습니다.

또한 각 노드 구조체에 visited 플래그를 추가해 방문 여부를 노드 자체에 저장하면, 별도의 해시 셋 없이도 방문 관리를 할 수 있어 시스템 부담을 더욱 덜 수 있습니다.

예제 코드 2 — unordered_map으로 부모 포인터 저장

다음은 개선된 방식을 구현한 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
    bool visited;
};

void postOrderTraversal(Node* root) {
    Node* n = root;
    unordered_map<Node*, Node*> postorder;
    postorder.insert(pair<Node*, Node*>(root, nullptr));
    while (n) {
        if (n->left && postorder.find(n->left) == postorder.end()) {
            postorder.insert(pair<Node*, Node*>(n->left, n));
            n = n->left;
        }
        else if (n->right && postorder.find(n->right) == postorder.end()) {
            postorder.insert(pair<Node*, Node*>(n->right, n));
            n = n->right;
        }
        else {
            cout<<n->data<<"\t";
            n = (postorder.find(n))->second;
        }
    }
}

struct Node* insertNode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->visited = false;
    return (node);
}

int main() {
    struct Node* root = insertNode(6);
    root->left = insertNode(2);
    root->right = insertNode(9);
    root->left->left = insertNode(8);
    root->left->right = insertNode(4);
    root->right->left = insertNode(7);
    root->right->left->left = insertNode(13);
    cout<<"Post Order Traversal of the binary tree :\n";
    postOrderTraversal(root);
    return 0;
}

출력 결과

Post Order Traversal of the binary tree :
8    4    2    13    7    9    6

마무리

두 방법 모두 시간 복잡도는 O(n)이며, 방문 정보를 저장하는 자료구조 때문에 공간 복잡도 역시 O(n)입니다. 재귀와 스택 없이도 후위 순회를 정확하게 수행할 수 있다는 점이 이 기법의 핵심이며, 특히 unordered_map에 부모 포인터를 저장하는 두 번째 방법이 불필요한 재탐색을 줄여 더 효율적입니다.