C++で二分木（BST以外）に重複する値が存在するかどうかを確認する方法

ここでは、二分木（バイナリツリー）が二分探索木（BST）ではない場合を想定します。この二分木の中に、同じ値を持つノードが2つ以上存在するかどうかを判定する必要があります。

BSTであれば中順走査（in-order traversal）によって値が昇順に並ぶため簡単に確認できますが、通常の二分木にはその性質がありません。そこで本記事ではハッシュセットを活用した効率的な解法を紹介します。

アルゴリズムの考え方

基本的なアプローチは以下の通りです。

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.";
}

実行結果

上記の例では、ルート直下の左子と右子がどちらも値 20 を持っているため、重複が検出されます。

The tree has duplicate elements.

計算量について

• 時間計算量： 各ノードを1回ずつ訪れ、ハッシュセットへの検索・挿入は平均 O(1) で行えるため、全体の計算量は O(n) となります（n はノード数）。
• 空間計算量： ハッシュセットに最大 n 個の値を格納する可能性があるため、O(n) の追加メモリが必要です。

まとめ

二分探索木ではない通常の二分木でも、ハッシュセットを使えば1回の走査で効率的に重複値を検出できます。再帰的な深さ優先探索（DFS）と組み合わせることで、コードもシンプルかつ読みやすくなります。大規模な木構造を扱う場合にも有効なテクニックなので、ぜひ覚えておきましょう。