C++로 이진 트리에서 가장 깊은 왼쪽 리프 노드 찾는 방법

이 튜토리얼에서는 이진 트리(binary tree)에서 가장 깊은 왼쪽 리프 노드(deepest left leaf node)를 찾는 방법을 알아보겠습니다. 먼저 예제로 사용할 이진 트리를 살펴보겠습니다.

   A
      B    C
D       E       F
                     G

위 트리에서 가장 깊은 왼쪽 리프 노드는 무엇일까요? 정답은 D입니다. 그렇다면 이를 프로그램으로 어떻게 찾을 수 있을까요? 문제 해결 절차를 단계별로 살펴보겠습니다.

문제 해결 접근 방식

문자 데이터(char)와 왼쪽·오른쪽 자식 포인터를 가지는 Node 구조체를 작성합니다.
더미 데이터로 이진 트리를 초기화합니다.
트리에서 가장 깊은 왼쪽 노드를 찾는 재귀 함수를 작성합니다. 이 함수는 세 개의 인자를 받습니다: 루트 노드, 현재 노드가 왼쪽 자식인지 여부(isLeftNode), 그리고 결과 노드를 저장할 포인터입니다.
현재 노드가 왼쪽 자식이면서 동시에 리프 노드(자식이 없는 노드)라면, 결과 노드를 현재 노드로 갱신합니다.
왼쪽 서브트리에 대해 재귀 함수를 호출하되, 왼쪽 자식임을 표시하는 플래그를 true로 전달합니다.
오른쪽 서브트리에 대해서도 재귀 함수를 호출하되, 플래그는 false로 전달합니다.
탐색이 끝난 후 결과 노드가 null이라면, 조건을 만족하는 노드가 트리에 존재하지 않는 것입니다.
반대로 결과 노드가 존재한다면, 해당 노드의 데이터를 출력합니다.

구현 예제

지금까지 설명한 로직을 C++ 코드로 구현해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

struct Node {
   char data;
   struct Node *left, *right;
};

Node *addNewNode(char data) {
   Node *newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}

void getDeepestLeftLeafNode(Node *root, bool isLeftNode, Node **resultPointer) {
   if (root == NULL) {
      return;
   }
   if (isLeftNode && !root->left && !root->right) {
      *resultPointer = root;
      return;
   }
   getDeepestLeftLeafNode(root->left, true, resultPointer);
   getDeepestLeftLeafNode(root->right, false, resultPointer);
}

int main() {
   Node* root = addNewNode('A');
   root->left = addNewNode('B');
   root->right = addNewNode('C');
   root->left->left = addNewNode('D');
   root->right->left = addNewNode('E');
   root->right->right = addNewNode('F');
   root->right->left->right = addNewNode('G');

   Node *result = NULL;
   getDeepestLeftLeafNode(root, false, &result);

   if (result) {
      cout << "가장 깊은 왼쪽 자식 노드는 " << result->data << endl;
   }
   else {
      cout << "주어진 트리에는 왼쪽 리프 노드가 없습니다" << endl;
   }
   return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

가장 깊은 왼쪽 자식 노드는 D

동작 원리 정리

이 알고리즘의 핵심은 재귀적으로 트리를 순회하면서 두 가지 조건을 동시에 확인하는 것입니다. 첫째, 현재 노드가 부모의 왼쪽 자식이어야 하고, 둘째, 리프 노드(양쪽 자식이 모두 없는 노드)여야 합니다. 재귀 호출 시 왼쪽으로 내려갈 때는 플래그를 true로, 오른쪽으로 내려갈 때는 false로 전달하기 때문에, 조건을 만족하는 노드를 만나면 해당 노드가 결과에 저장됩니다. 트리를 깊이 우선으로 탐색하며 마지막으로 발견된 왼쪽 리프가 곧 '가장 깊은' 왼쪽 리프 노드가 됩니다.

마무리

이번 튜토리얼에서는 C++를 사용하여 이진 트리에서 가장 깊은 왼쪽 리프 노드를 찾는 방법을 배웠습니다. 재귀와 플래그 변수만으로 간단하게 해결할 수 있는 문제이므로, 직접 코드를 변형해 보면서 이해를 깊게 해보시기 바랍니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.