이 문서에서는 이진 트리의 핵심 개념과 다양한 문제 해결 기법을 심층적으로 다룹니다. 노드 구조 정의부터 재귀/비재귀 순회, 그리고 여러 트리 유형 판별 알고리즘과 고급 주제까지 단계별로 살펴봅니다.
1. 이진 트리 노드 구조
이진 트리의 기본 단위는 노드(Node)이며, 각 노드는 데이터와 왼쪽, 오른쪽 자식 노드를 가리키는 포인터로 구성됩니다.
// C++ 이진 트리 노드 정의
struct Node {
int data;
Node* left;
Node* right;
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
2. 재귀 순회 (Recursive Traversal)
재귀를 이용한 순회는 함수 호출 스택을 활용합니다. 각 노드는 세 번의 방문 기회를 가지며, 이 시점에 따라 전위, 중위, 후위 순회로 나뉩니다.
- 전위 순회 (Preorder): 루트 → 왼쪽 → 오른쪽
- 중위 순회 (Inorder): 왼쪽 → 루트 → 오른쪽
- 후위 순회 (Postorder): 왼쪽 → 오른쪽 → 루트
3. 비재귀 순회 (Iterative Traversal)
스택(Stack)을 직접 구현하여 재귀 호출의 동작을 모방합니다.
3.1 비재귀 전위 순회
void iterativePreorder(Node* root) {
if (!root) return;
stack<Node*> st;
st.push(root);
while (!st.empty()) {
Node* current = st.top(); st.pop();
cout << current->data << " ";
// 오른쪽을 먼저 push (LIFO 특성)
if (current->right) st.push(current->right);
if (current->left) st.push(current->left);
}
}
3.2 비재귀 후위 순회
void iterativePostorder(Node* root) {
if (!root) return;
stack<Node*> st1, st2;
st1.push(root);
while (!st1.empty()) {
Node* current = st1.top(); st1.pop();
st2.push(current);
if (current->left) st1.push(current->left);
if (current->right) st1.push(current->right);
}
while (!st2.empty()) {
cout << st2.top()->data << " ";
st2.pop();
}
}
3.3 비재귀 중위 순회
void iterativeInorder(Node* root) {
stack<Node*> st;
Node* current = root;
while (current || !st.empty()) {
// 왼쪽 끝까지 이동
while (current) {
st.push(current);
current = current->left;
}
current = st.top(); st.pop();
cout << current->data << " ";
current = current->right;
}
}
4. 레벨 순회 (Level Order Traversal)
큐(Queue)를 사용하여 BFS 방식으로 트리를 탐색합니다.
#include <queue>
void levelOrder(Node* root) {
if (!root) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front(); q.pop();
cout << current->data << " ";
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
4.1 트리의 최대 너비 구하기
레벨 순회를 변형하여 각 레벨의 노드 개수를 확인합니다.
int getMaxWidth(Node* root) {
if (!root) return 0;
queue<Node*> q;
q.push(root);
int maxWidth = 0;
while (!q.empty()) {
int levelSize = q.size();
maxWidth = max(maxWidth, levelSize);
for (int i = 0; i < levelSize; i++) {
Node* current = q.front(); q.pop();
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
return maxWidth;
}
5. 트리 유형 판별
5.1 이진 검색 트리 (BST) 판별
중위 순회 결과가 오름차순인지 확인합니다.
bool isBST(Node* root, Node* minNode = nullptr, Node* maxNode = nullptr) {
if (!root) return true;
if (minNode && root->data <= minNode->data) return false;
if (maxNode && root->data >= maxNode->data) return false;
return isBST(root->left, minNode, root) &&
isBST(root->right, root, maxNode);
}
5.2 완전 이진 트리 판별
BFS를 사용하여 두 가지 조건을 검사합니다: (1) 오른쪽 자식만 있는 노드가 없어야 함, (2) 자식이 없는 노드 이후에는 모든 노드가 리프 노드여야 함.
bool isCompleteTree(Node* root) {
if (!root) return true;
queue<Node*> q;
q.push(root);
bool leafMode = false;
while (!q.empty()) {
Node* current = q.front(); q.pop();
Node* leftChild = current->left;
Node* rightChild = current->right;
// 조건 1: 오른쪽만 있고 왼쪽이 없는 경우
if (!leftChild && rightChild) return false;
// 조건 2: 리프 모드에서 자식이 있는 경우
if (leafMode && (leftChild || rightChild)) return false;
if (leftChild) q.push(leftChild);
if (rightChild) q.push(rightChild);
// 자식이 하나라도 없으면 리프 모드 활성화
if (!leftChild || !rightChild) leafMode = true;
}
return true;
}
5.3 포화 이진 트리 판별
노드 개수(N)와 높이(H)가 N = 2^H - 1 관계를 만족하는지 확인합니다.
bool isFullTree(Node* root) {
if (!root) return true;
int height = 0, nodeCount = 0;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
nodeCount += levelSize;
height++;
for (int i = 0; i < levelSize; i++) {
Node* current = q.front(); q.pop();
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
return nodeCount == (1 << height) - 1;
}
6. 트리 DP (Tree DP) 패턴
이 패턴은 재귀적으로 왼쪽/오른쪽 서브트리로부터 정보를 요청하고 합쳐서 문제를 해결합니다.
6.1 균형 이진 트리 판별
각 서브트리의 높이와 균형 여부를 반환하는 구조체를 정의합니다.
struct BalanceInfo {
bool isBalanced;
int height;
};
BalanceInfo checkBalance(Node* root) {
if (!root) return {true, 0};
BalanceInfo left = checkBalance(root->left);
BalanceInfo right = checkBalance(root->right);
bool balanced = left.isBalanced && right.isBalanced &&
abs(left.height - right.height) <= 1;
int height = max(left.height, right.height) + 1;
return {balanced, height};
}
6.2 BST 판별 (DP 방식)
struct BSTInfo {
bool isBST;
int minVal;
int maxVal;
};
BSTInfo checkBST(Node* root) {
if (!root) return {true, INT_MAX, INT_MIN};
BSTInfo left = checkBST(root->left);
BSTInfo right = checkBST(root->right);
bool valid = left.isBST && right.isBST &&
left.maxVal < root->data &&
root->data < right.minVal;
int minVal = min({root->data, left.minVal, right.minVal});
int maxVal = max({root->data, left.maxVal, right.maxVal});
return {valid, minVal, maxVal};
}
6.3 포화 트리 판별 (DP 방식)
struct TreeInfo {
int height;
int nodeCount;
};
TreeInfo getTreeInfo(Node* root) {
if (!root) return {0, 0};
TreeInfo left = getTreeInfo(root->left);
TreeInfo right = getTreeInfo(root->right);
int height = max(left.height, right.height) + 1;
int nodeCount = left.nodeCount + right.nodeCount + 1;
return {height, nodeCount};
}
bool isFullTreeDP(Node* root) {
if (!root) return true;
TreeInfo info = getTreeInfo(root);
return info.nodeCount == (1 << info.height) - 1;
}
주의사항: 트리 DP 패턴은 모든 문제에 적용 가능하지 않습니다. 예를 들어, 트리에서 데이터의 중앙값을 찾는 문제는 지역 정보만으로 전역 해답을 도출할 수 없어 이 패턴이 적합하지 않습니다.
7. 고급 문제
7.1 최소 공통 조상 (LCA)
두 노드가 주어졌을 때, 가장 가까운 공통 조상을 찾습니다.
Node* findLCA(Node* root, Node* p, Node* q) {
if (!root || root == p || root == q) return root;
Node* left = findLCA(root->left, p, q);
Node* right = findLCA(root->right, p, q);
if (left && right) return root; // p, q가 서로 다른 서브트리에 있음
return left ? left : right; // 둘 중 하나가 조상임
}
7.2 후속 노드 (Inorder Successor)
중위 순회에서 특정 노드 다음에 오는 노드를 찾습니다. (부모 포인터가 있다고 가정)
struct NodeWithParent {
int data;
NodeWithParent* left;
NodeWithParent* right;
NodeWithParent* parent;
};
NodeWithParent* getSuccessor(NodeWithParent* node) {
if (!node) return nullptr;
// Case 1: 오른쪽 자식이 있는 경우
if (node->right) {
NodeWithParent* current = node->right;
while (current->left) current = current->left;
return current;
}
// Case 2: 오른쪽 자식이 없는 경우
NodeWithParent* parent = node->parent;
while (parent && parent->right == node) {
node = parent;
parent = parent->parent;
}
return parent;
}
7.3 직렬화와 역직렬화
트리를 문자열로 변환하고 다시 복원합니다.
// 직렬화: 전위 순회 사용, NULL은 "null"로 표시
string serialize(Node* root) {
if (!root) return "null,";
return to_string(root->data) + "," +
serialize(root->left) +
serialize(root->right);
}
// 역직렬화 도우미
Node* deserializeHelper(istringstream& ss) {
string token;
getline(ss, token, ',');
if (token == "null") return nullptr;
Node* node = new Node(stoi(token));
node->left = deserializeHelper(ss);
node->right = deserializeHelper(ss);
return node;
}
Node* deserialize(const string& data) {
istringstream ss(data);
return deserializeHelper(ss);
}
7.4 종이 접기 문제 (Microsoft 인터뷰)
종이를 N번 접었을 때 생기는 주름 방향은 이진 트리 구조로 모델링할 수 있습니다. 각 노드는 '위' 또는 '아래' 방향을 가지며, 중위 순회가 실제 주름 패턴과 일치합니다.
void printCreases(int folds) {
if (folds <= 0) return;
printCreasesRecursive(folds, true); // true = 아래 방향
}
void printCreasesRecursive(int n, bool isDown) {
if (n == 1) {
cout << (isDown ? "down " : "up ");
return;
}
printCreasesRecursive(n - 1, true); // 왼쪽: 항상 down
cout << (isDown ? "down " : "up ");
printCreasesRecursive(n - 1, false); // 오른쪽: 항상 up
}
이 재귀적 접근 방식은 O(N) 공간 복잡도를 가지며, 직접 시뮬레이션의 O(2^N)에 비해 매우 효율적입니다.