Insert into a Binary Search Tree ใน C++

โจทย์: Insert into a Binary Search Tree

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

ตัวอย่าง: BST เดิม: [4,2,7,1,3] แทรก 5 → ผลลัพธ์: [4,2,7,1,3,5]

อัลกอริทึม: Recursive Insertion

1. ฟังก์ชัน insertIntoBST(root, val) แบบ recursive
2. ถ้า root == nullptr: สร้างโหนดใหม่ค่า val ส่งคืนเป็น root ใหม่
3. ถ้า root->val > val: แทรกไปซ้าย → root->left = insertIntoBST(root->left, val)
4. มิฉะนั้น (root->val < val): แทรกไปขวา → root->right = insertIntoBST(root->right, val)
5. ส่งคืน root

สมมติฐาน: BST ไม่มีค่าซ้ำ (no duplicates) หากมีค่าซ้ำ ปกติจะแทรกไปขวา (หรือซ้าย ตามนิยาม)

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

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        if (root->val > val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};

// Helper: สร้างต้นไม้จาก level-order (สำหรับทดสอบ)
TreeNode* make_tree(vector<int> v) {
    if (v.empty()) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* curr = q.front(); q.pop();
        if (i < v.size() && v[i] != -1) {
            curr->left = new TreeNode(v[i]);
            q.push(curr->left);
        }
        i++;
        if (i < v.size() && v[i] != -1) {
            curr->right = new TreeNode(v[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}

// Helper: พิมพ์ต้นไม้ level-order
void print_tree(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    cout << "[";
    bool first = true;
    while (!q.empty()) {
        TreeNode* curr = q.front(); q.pop();
        if (!first) cout << ",";
        first = false;
        if (curr) {
            cout << curr->val;
            q.push(curr->left);
            q.push(curr->right);
        } else {
            cout << "null";
        }
    }
    cout << "]" << endl;
}

int main() {
    Solution ob;
    vector<int> v = {4, 2, 7, 1, 3};
    TreeNode* root = make_tree(v);
    cout << "ต้นไม้เดิม: ";
    print_tree(root);
    TreeNode* new_root = ob.insertIntoBST(root, 5);
    cout << "หลังแทรก 5: ";
    print_tree(new_root);
    return 0;
}

Input

[4,2,7,1,3] 5

Output

[4,2,7,1,3,5]

ความซับซ้อน (Complexity)

• เวลา: O(h) โดย h = ความสูงของต้นไม้ (เฉลี่ย O(log n) สำหรับต้นไม้สมดุล, สูงสุด O(n) สำหรับ skewed tree)
• พื้นที่: O(h) เรียกซ้ำ recursive stack

แก้ไขจากโค้ดต้นฉบับ: โค้ดต้นฉบับมีฟังก์ชัน insert() แบบ level-order (สำหรับ complete binary tree) ไม่ใช่ BST insertion และมีบั๊กหลายจุด ได้เขียนฟังก์ชัน make_tree และ print_tree ใหม่ให้ถูกต้อง