การแปลง Binary Tree เป็น Binary Search Tree ด้วย STL Set ใน C++

โจทย์ปัญหา

ได้รับ Binary Tree ให้แปลงเป็น Binary Search Tree (BST) โดย รักษาโครงสร้างต้นไม้เดิมไว้ (โหนดเดิมอยู่ที่เดิม แค่เปลี่ยนค่า)

ตัวอย่าง

Input Tree:

Output BST:

แนวคิดการแก้ปัญหา (ใช้ STL Set)

Inorder Traversal Binary Tree เดิม เก็บค่าทุกโหนดลงใน std::set (Auto-sorted, Unique)
Inorder Traversal อีกครั้ง นำค่าจาก Set (เรียงเล็กไปใหญ่) มาใส่แทนค่าเดิมในโหนด
ลบค่าที่ใช้แล้วออกจาก Set ทีละตัว

ทำไมใช้ Set? Set ใน C++ STL ใช้ Self-Balancing BST (Red-Black Tree) ทำให้ Insert/Erase/Access ใช้เวลา O(log n) และเก็บค่าอัตโนมัติ

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

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

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

// 1. เก็บค่า Inorder ลง Set
void storeInorderInSet(Node* root, set<int>& s) {
    if (!root) return;
    storeInorderInSet(root->left, s);
    s.insert(root->data);  // O(log n)
    storeInorderInSet(root->right, s);
}

// 2. นำค่าจาก Set กลับเข้า Tree (Inorder)
void setToBST(set<int>& s, Node* root) {
    if (!root) return;
    setToBST(s, root->left);

    auto it = s.begin();
    root->data = *it;   // ใส่ค่าน้อยที่สุดที่เหลือ
    s.erase(it);        // ลบออกจาก Set

    setToBST(s, root->right);
}

// Main Conversion Function
void binaryTreeToBST(Node* root) {
    set<int> s;
    storeInorderInSet(root, s);  // O(n log n)
    setToBST(s, root);           // O(n log n)
}

// Helper Functions
Node* newNode(int data) {
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = nullptr;
    return temp;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = newNode(6);
    root->left = newNode(8);
    root->right = newNode(10);
    root->right->left = newNode(11);
    root->left->left = newNode(2);
    root->left->right = newNode(7);
    root->right->right = newNode(12);

    /* Tree:
          6
         / \
        8  10
       /\  / \
      2 7 11 12
    */

    binaryTreeToBST(root);

    cout << "Inorder traversal of BST is: ";
    inorder(root);  // Should be sorted: 2 6 7 8 10 11 12
    return 0;
}

ผลลัพธ์

Inorder traversal of BST is: 2 6 7 8 10 11 12

Complexity Analysis

Time: O(n log n) (n = จำนวนโหนด, Set operations = log n)
Space: O(n) สำหรับ Set + Recursion Stack

คำอธิบายเพิ่มเติม

วิธีนี้ง่ายกว่าวิธี Array-based (Sort Array + Inorder) เพราะไม่ต้องจัดการ Index เอง
ถ้าอนุญาต Duplicate Values ให้ใช้ multiset แทน set
Inorder Traversal ของ BST จะได้ค่าที่เรียงจากน้อยไปมากเสมอ