C++로 일반 이진 트리(BST 아님)에서 중복 값 확인하기

일반적인 이진 트리가 주어졌다고 가정해 봅시다. 이 트리는 이진 탐색 트리(BST)가 아니므로 노드 값 사이에 특정한 정렬 규칙이 없습니다. 따라서 트리 안에 동일한 값이 두 번 이상 등장하는지 확인하려면 다른 방식의 접근이 필요합니다.

가장 효율적인 해결 방법은 해싱(hashing)을 활용하는 것입니다. 트리를 순회하면서 각 노드의 값을 해시 집합(unordered_set)에 저장하고, 어떤 노드의 값이 이미 집합에 존재한다면 그 즉시 중복이 있다고 판단하여 true를 반환합니다. 모든 노드를 순회했는데도 중복이 발견되지 않으면 false를 반환합니다.

알고리즘 접근 방법

동작 과정은 다음과 같습니다.

1. 빈 unordered_set을 생성합니다.
2. 트리를 깊이 우선 방식으로 순회합니다.
3. 현재 노드의 값이 집합에 이미 존재하면 중복이므로 true를 반환합니다.
4. 존재하지 않으면 값을 집합에 삽입한 뒤, 왼쪽과 오른쪽 자식 노드를 재귀적으로 탐색합니다.
5. 모든 노드를 확인할 때까지 중복이 없으면 false를 반환합니다.

C++ 구현 예제

#include <iostream>
#include <unordered_set>
using namespace std;
class Node {
    public:
    int data;
    Node *left;
    Node *right;
};
Node* getNode(int data){
    Node *newNode = new Node;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
bool hasDuplicateHelper(Node *root, unordered_set<int> &s){
    if(root == NULL)
        return false;
    if (s.find(root->data) != s.end())
        return true;
    s.insert(root->data);
    return hasDuplicateHelper(root->left, s) || hasDuplicateHelper(root->right, s);
}
bool hasDuplicate(Node *root){
    unordered_set<int> s;
    return hasDuplicateHelper(root, s);
}
int main() {
    Node *root = getNode(10);
    root->left = getNode(20);
    root->right = getNode(20);
    root->left->left = getNode(30);
    if (hasDuplicate(root))
        cout << "The tree has duplicate elements.";
    else
        cout << "The tree has no duplicate elements.";
}

출력 결과

The tree has duplicate elements.

위 예제에서 루트의 왼쪽 자식과 오른쪽 자식이 모두 20으로 동일하기 때문에, 프로그램은 트리에 중복 요소가 존재한다고 출력합니다.

복잡도 분석

시간 복잡도: O(n) — 각 노드를 정확히 한 번씩 방문하며, 해시 집합에서의 탐색과 삽입은 평균 O(1)입니다.

공간 복잡도: O(n) — 최악의 경우 모든 노드의 값이 고유하여 해시 집합에 n개의 값이 저장됩니다. 또한 재귀 호출 스택에도 트리의 높이만큼 공간이 사용됩니다.