이진 트리 Q8. 증손자가 있는 노드 찾기

자료구조 C 실습 · 이진 트리 · Q8

이진 트리 Q8. 증손자가 있는 노드 찾기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section E Binary Tree hasGreatGrandchild

어떤 노드가 적어도 한 명 이상의 증손자(great-grandchild)를 가지는지 검사하고, 그런 노드의 값을 출력하는 문제다. 현재 노드 기준으로 깊이 3 아래까지 자식 유무를 확인해야 한다. 결국 '손자의 자식이 존재하는가'를 코드로 풀어쓴 문제다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Binary_Tree\Q8_E_BT.c

대상 함수: hasGreatGrandchild

카테고리: 이진 트리

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Create a binary tree.
• 2: Find the great grandchildren of the binary tree.
• 0: Quit
• The resulting binary tree is
• The values stored in all nodes of the tree that has at least one great-grandchild are
• %d

핵심 구현 흐름

STEP 1

현재 노드의 각 자식-손자-증손자 경로를 조합해 존재 여부를 검사한다.

STEP 2

조건을 만족하면 현재 노드 값을 출력한다.

STEP 3

이후 왼쪽·오른쪽 서브트리에 대해 같은 검사를 반복한다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: hasGreatGrandchild

int hasGreatGrandchild(BTNode *node)
{
    if (node == NULL)
    {
        return 0;
    }

    if (
        (node->left != NULL &&
         node->left->left != NULL &&
         (node->left->left->left != NULL || node->left->left->right != NULL)) ||

        (node->left != NULL &&
         node->left->right != NULL &&
         (node->left->right->left != NULL || node->left->right->right != NULL)) ||

        (node->right != NULL &&
         node->right->left != NULL &&
         (node->right->left->left != NULL || node->right->left->right != NULL)) ||

        (node->right != NULL &&
         node->right->right != NULL &&
         (node->right->right->left != NULL || node->right->right->right != NULL))
       )
    {
        printf("%d ", node->item);
    }

    hasGreatGrandchild(node->left);
    hasGreatGrandchild(node->right);

    return 0;
}

구현할 때 체크할 점

• 깊이 3을 확인하는 동안 NULL 검사를 빼먹으면 접근 오류가 난다.
• 현재 노드 자신이 아니라 '증손자를 가진 조상 노드'를 출력해야 한다는 점을 놓치기 쉽다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 현재 노드 기준으로 깊이 3 아래까지 자식 유무를 확인해야 한다. 결국 '손자의 자식이 존재하는가'를 코드로 풀어쓴 문제다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.