ตรวจสอบ Binary Tree (ไม่ใช่ BST) มีค่าซ้ำใน C++

ปัญหา

ให้ Binary Tree ธรรมดา (ไม่ใช่ BST) ตรวจสอบว่ามีค่าโหนดซ้ำกันหรือไม่

วิธีแก้: Hashing (Hash Set)

1. ท่อง Tree (Preorder, Inorder, Postorder, หรือ Level-order ก็ได้)
2. สำหรับแต่ละโหนด:
   • ถ้าค่าอยู่ใน Hash Set แล้ว → มีค่าซ้ำ return true
   • เพิ่มค่าลง Hash Set
3. จบการท่อง → ไม่มีค่าซ้ำ

ตัวอย่างโค้ด C++

#include <iostream>
#include <unordered_set>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

bool hasDuplicateHelper(Node* root, unordered_set& seen) {
    if (!root) return false;
    
    // ตรวจสอบค่าซ้ำ
    if (seen.count(root->data))
        return true;
    
    seen.insert(root->data);
    
    // ท่องต่อ (Short-circuit: ถ้าซ้ายเจอซ้ำ ไม่ต้องไปขวา)
    return hasDuplicateHelper(root->left, seen) || 
           hasDuplicateHelper(root->right, seen);
}

bool hasDuplicate(Node* root) {
    unordered_set seen;
    return hasDuplicateHelper(root, seen);
}

int main() {
    // Tree ที่มีค่าซ้ำ: 20 ปรากฏ 2 ครั้ง
    Node* root = new Node(10);
    root->left = new Node(20);
    root->right = new Node(20); // ซ้ำ!
    root->left->left = new Node(30);
    
    if (hasDuplicate(root))
        cout << "Tree has duplicate values" << endl;
    else
        cout << "Tree has no duplicate values" << endl;
    
    // Tree ไม่มีค่าซ้ำ
    Node* root2 = new Node(10);
    root2->left = new Node(20);
    root2->right = new Node(30);
    root2->left->left = new Node(40);
    
    if (hasDuplicate(root2))
        cout << "Tree2 has duplicate values" << endl;
    else
        cout << "Tree2 has no duplicate values" << endl;
    
    return 0;
}

ผลลัพธ์

Tree has duplicate values
Tree2 has no duplicate values

ความซับซ้อน

• เวลา: O(n) - เยี่ยมชมทุกโหนด 1 ครั้ง, Hash set operations O(1) average
• พื้นที่: O(n) - Hash set เก็บค่าทั้งหมด + Recursion stack O(h)

วิธีอื่น (ไม่ใช้ Extra Space)

ถ้าห้ามใช้ Hash Set ให้ท่องทุกคู่โหนด (O(n²)) หรือแปลงเป็น array เรียงลำดับ (O(n log n) พื้นที่ O(n))

กรณีพิเศษ: BST

ถ้าเป็น BST สามารถตรวจสอบค่าซ้ำได้ง่ายกว่า: ใน Inorder traversal ค่าต้องเพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) ถ้าเจอค่าเท่ากัน → มีซ้ำ