[WIL-250619] 재귀 호출, 스택에 직접 그려보니 보이더라 – 트리 탐색 구현기

이진 트리에서 홀수 노드의 합 구하기

• 이진 트리 구조에서 모든 홀수 값 노드를 재귀적으로 더하는 함수를 구현했다.
• 이 문제는 재귀 탐색을 통해 트리 전체를 순회하며 홀수 값을 누적하는 구조이다.

문제의 트러블 슈팅

• 재귀

“그래프 방식에서 재귀를 호출하면 어떻게 될지?”

재귀 호출의 흐름을 큰 그림으로 이해하지 못함.

해결방법

1. 팀원에게 조언을 듣고 함께 시각화
2. 메모리 스택에 호출이 어떻게 쌓이는지 직접 그려보며 추적
3. 스스로 트리 구조를 따라가며 스택이 어떻게 쌓이고, 결과가 어떻게 돌아오는지 학습

문제설명

접근 방법

트리를 재귀적으로 순회하면서 다음을 수행:

1. 왼쪽/오른쪽 서브트리를 재귀 호출
2. 기저 조건을 만났을때 스택에 빠지면서 각 노드의 홀수인지 판단
3. 홀수이면 누적 result += node->item

완성코드

int sumOfOddNodes(BTNode *node)

{
     // 노드가 NULL이면 0을 반환한다 (기저 조건)
    if (node == NULL) return 0;

    // 왼쪽 서브트리의 홀수 합을 재귀적으로 구한다
    int left = sumOfOddNodes(node->left);

    // 오른쪽 서브트리의 홀수 합을 재귀적으로 구한다
    int right = sumOfOddNodes(node->right);

    // 결과를 저장할 변수 초기화
    int result = 0;

    // 현재 노드의 값이 홀수이면 result에 더한다
    if (node->item % 2 != 0) {
        result += node->item;
    }

    // 왼쪽/오른쪽 서브트리의 합을 result에 누적
    result += left;
    result += right;

    // 최종 결과 반환
    return result;
}

트리 구조 기반 호출 흐름

🔹 1단계: sumOfOddNodes(50) 호출

• 현재 노드: 50
• 왼쪽 자식 확인 전, 노드가 NULL인지 먼저 검사
• 왼쪽 서브트리로 재귀 진입 시작

---

🔹 2단계: 왼쪽 서브트리 sumOfOddNodes(40) 호출

• 현재 노드: 40
• 왼쪽 자식 sumOfOddNodes(11) 호출
  • 11은 홀수 → result = 11
  • 11의 왼쪽, 오른쪽은 NULL → 각각 기저 조건에서 return 0
• 오른쪽 자식 sumOfOddNodes(35) 호출
  • 35는 홀수 → result = 35
  • 35의 왼쪽, 오른쪽도 NULL → 기저 조건에서 return 0

왼쪽 서브트리 합계: 11 + 35 = 46

---

🔹 3단계: 오른쪽 서브트리 sumOfOddNodes(60) 호출

• 현재 노드: 60 (짝수 → 더하지 않음)
• 왼쪽 자식 sumOfOddNodes(80) 호출
  • 자식은 모두 NULL → 기저 조건에서 return 0
• 오른쪽 자식 sumOfOddNodes(85) 호출
  • 85는 홀수 → result = 85
  • 자식은 모두 NULL → 기저 조건에서 return 0

오른쪽 서브트리 합계: 0 + 85 = 85

---

🔹 4단계: 루트(50)로 복귀 → 최종 합산

• 왼쪽 결과: 46
• 오른쪽 결과: 85
• 루트 50은 짝수 → 포함 X

최종 결과: 46 + 85 = 131

배운 점 & 느낀 점 (Reflection)

• 후위 순회(post-order) 방식의 재귀는 **"끝까지 들어갔다가, 다시 올라오면서 계산한다"**는 구조를 체득함.
• 코드보다 호출 흐름을 시각적으로 그리는 것이 진짜 이해로 이어졌다.
• 복잡해보이는 재귀 문제도 기저 조건부터 차근차근 따라가면 구조가 단순해진다.