서론: 재귀에 대한 솔직한 고백

재귀를 코딩할 때 종종 이런 경험이 있다. 코드는 작동하지만, "왜 이게 맞는지"는 설명하기 어렵다. 예를 들어:

• 왜 트리를 해제할 때 후위 순회를 써야 할까?
• 어떤 문제에서는 논리합(||)을 쓰고, 어떤 문제에서는 논리곱(&&)을 쓸까?
• 함수를 분리해서 작성해야 하는 경우는 언제일까?

이 글은 이 모든 질문에 답하며, 이진 트리 재귀의 핵심 모델을 기반으로 코드 설계 원리를 명확히 한다.

핵심 개념: 재귀의 세 가지 패턴

모든 이진 트리 재귀 문제는 아래 세 가지 패턴 중 하나로 귀결된다.

1. 집계형 (합산 패턴)

현재 노드의 결과는 좌우 서브트리의 결과를 더한 값에 현재 값을 반영한다.

결과 = left_result + right_result [+ 현재 값]

2. 존재형 (OR 패턴)

하나라도 조건을 만족하면 전체가 성립한다. 즉, "하나 찾으면 끝".

결과 = left_check || right_check

3. 구조 일치형 (AND 패턴)

모든 하위 조건이 동시에 만족되어야 한다. 하나라도 틀리면 실패.

결과 = left_valid && right_valid

이 세 가지 패턴은 이후 모든 예제의 기반이 된다.

기초 연산: 생성과 소멸

노드 생성

단순한 메모리 할당과 초기화 과정이다.

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if (!node) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    node->val = value;
    node->left = node->right = NULL;
    return node;
}

트리 해제 (후위 순회의 중요성)

트리를 삭제할 때는 반드시 후위 순회 방식을 사용해야 한다.

void destroyTree(TreeNode* root) {
    if (!root) return;
    
    destroyTree(root->left);   // 자식 먼저
    destroyTree(root->right);
    free(root);                // 본인 나중에
}

왜 후위인가?
포인터를 해제한 후 접근하면 미정의 동작(UB)이 발생한다. 부모가 자식을 참조하고 있으므로, 자식을 먼저 제거하고 마지막에 부모를 해제해야 안전하다. 이는 메모리 누수와 댕글링 포인터를 막는 핵심 원칙이다.

순회: 재귀의 첫걸음

기본적인 전위, 중위, 후위 순회는 모두 유사한 구조를 가진다.

// 전위 순회
void preorder(TreeNode* root) {
    if (!root) {
        printf(" N ");
        return;
    }
    printf(" %d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

// 중위 순회
void inorder(TreeNode* root) {
    if (!root) {
        printf(" N ");
        return;
    }
    inorder(root->left);
    printf(" %d ", root->val);
    inorder(root->right);
}

// 후위 순회
void postorder(TreeNode* root) {
    if (!root) {
        printf(" N ");
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf(" %d ", root->val);
}

집계형 문제: 카운팅과 레벨 계산

총 노드 수, 리프 노드 수, 특정 레벨의 노드 수 등은 모두 덧셈 기반의 재귀로 해결된다.

총 노드 수

int countNodes(TreeNode* root) {
    return root ? countNodes(root->left) + countNodes(root->right) + 1 : 0;
}

리프 노드 수

자식이 없는 노드만 카운트한다. 재귀적으로 각 서브트리에서 리프를 찾아 합산.

int countLeaves(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

k번째 레벨의 노드 수

레벨을 내려갈수록 k를 감소시키며, k==1일 때 카운트 시작.

int countAtLevel(TreeNode* root, int k) {
    if (!root || k < 1) return 0;
    if (k == 1) return 1;
    return countAtLevel(root->left, k - 1) + countAtLevel(root->right, k - 1);
}

탐색형 문제: 값 찾기

특정 값을 가진 노드를 찾는 문제는 "존재 여부"를 판단하는 OR 패턴을 따른다.

TreeNode* findValue(TreeNode* root, int target) {
    if (!root) return NULL;
    if (root->val == target) return root;

    TreeNode* found = findValue(root->left, target);
    if (found) return found;  // 왼쪽에서 찾으면 더 이상 오른쪽 탐색 X

    return findValue(root->right, target);
}

여기서 if (found) 조건은 단락 평가(short-circuiting)를 통해 불필요한 탐색을 막는다.

높이 계산: 최댓값 기반 재귀

트리의 높이는 좌우 서브트리 중 더 긴 쪽에 1을 더한 값이다.

int treeHeight(TreeNode* root) {
    if (!root) return 0;
    
    int leftH = treeHeight(root->left);
    int rightH = treeHeight(root->right);
    
    return (leftH > rightH ? leftH : rightH) + 1;
}

각 노드는 자신의 역할만 수행하며, 결과는 하위에서 상위로 전달된다. 이는 "상향식 처리"의 전형적인 사례다.

단일 값 트리 판별

모든 노드가 같은 값을 가져야 한다. 두 가지 접근 방법이 있다.

방법 1: 로컬 비교

자식이 있으면 그 값이 부모와 같은지 확인. 그러나 이 방식은 근본적인 일관성을 보장하지 못할 수 있다.

방법 2 (권장): 전역 기준 비교

루트의 값을 기준으로 모든 노드를 검사.

bool isUnivalCheck(TreeNode* node, int val) {
    if (!node) return true;
    if (node->val != val) return false;
    return isUnivalCheck(node->left, val) && isUnivalCheck(node->right, val);
}

bool isUnivalTree(TreeNode* root) {
    if (!root) return true;
    return isUnivalCheck(root, root->val);
}

구조 일치형 패턴(&&)을 사용해 모든 노드가 기준값과 일치해야 통과한다.

구조 비교 문제

동일 트리 판별

두 트리의 구조와 값이 완전히 동일한지 확인.

bool areIdentical(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    if (a->val != b->val) return false;
    return areIdentical(a->left, b->left) && areIdentical(a->right, b->right);
}

모든 조건이 동시에 만족되어야 하므로 AND 연산을 사용한다.

서브트리 포함 여부

첫 번째 트리 내에 두 번째 트리와 동일한 구조가 포함되는지 확인.

bool containsSubtree(TreeNode* big, TreeNode* small) {
    if (!big) return false;
    if (areIdentical(big, small)) return true;
    return containsSubtree(big->left, small) || containsSubtree(big->right, small);
}

포지션 탐색은 OR 패턴, 구조 매칭은 AND 패턴을 사용한다.

대칭 트리 (미러)

좌우가 서로 거울처럼 대칭인지 판단.

bool isMirror(TreeNode* left, TreeNode* right) {
    if (!left && !right) return true;
    if (!left || !right) return false;
    if (left->val != right->val) return false;
    return isMirror(left->left, right->right) && isMirror(left->right, right->left);
}

bool isSymmetric(TreeNode* root) {
    return !root || isMirror(root->left, root->right);
}

순회 확장: 배열에 저장

순회 결과를 배열에 복사할 때 인덱스는 포인터로 전달해야 변경이 반영된다.

void storePreorder(TreeNode* root, int* arr, int* idx) {
    if (!root) return;
    arr[(*idx)++] = root->val;
    storePreorder(root->left, arr, idx);
    storePreorder(root->right, arr, idx);
}

정적 변수나 전역 변수 사용은 여러 호출 시 누적되므로 비추천. 항상 매개변수로 상태를 전달하라.

최종 요약: 기억할 핵심 원칙

• 재귀는 현재 노드만 처리하고, 나머지는 하위 호출에 위임한다.
• 집계 → 덧셈 기반
• 존재 여부 → OR (||)
• 구조 일치 → AND (&&)
• 메모리 해제 → 후위 순회 필수
• NULL 체크 생략 금지: 재귀의 기저 조건은 반드시 명시

마무리: 진정한 이해란?

코드를 "작성할 수 있다"는 것과 "왜 그렇게 작성해야 하는지 설명할 수 있다"는 것은 다르다. 면접에서 자주 묻는 질문들은 바로 이런 근본 원리를 검증하기 위한 것이다:

• 왜 해제는 후위인가?
• 왜 isSame은 &&인가?
• 왜 find는 || 논리가 아닌가?

재귀는 단순한 기술이 아니라 사고 방식이다. "아는 척"이 아니라 "알고 있다는 증명"이 필요하다.