Insert vào Binary Search Tree trong C++

Cho một cây tìm kiếm nhị phân (BST). Viết phương thức chèn một node với giá trị cho trước, đảm bảo sau khi chèn cây vẫn là BST.

Ví dụ: Cây ban đầu [4,2,7,1,3], chèn 5 → cây mới [4,2,7,1,3,5].

Giải thuật (Đệ quy)

• Hàm insert(root, val):
• Nếu root == null: tạo node mới giá trị val làm root.
• Nếu root->val > val: root->left = insert(root->left, val).
• Ngược lại: root->right = insert(root->right, val).
• Trả về root.

Ví dụ code

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

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

// Hàm hỗ trợ in cây level-order
void tree_level_trav(TreeNode* root) {
    if (!root) return;
    cout << "[";
    queue<TreeNode*> q;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        TreeNode* curr = q.front(); q.pop();
        if (!curr) { q.push(NULL); continue; }
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
        cout << curr->val << ", ";
    }
    cout << "]" << endl;
}

int main() {
    Solution ob;
    vector<int> v = {4,2,7,1,3};
    // Giả sử make_tree xây dựng BST từ mảng level-order
    TreeNode* root = new TreeNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        // insert vào BST (bỏ qua code make_tree phức tạp)
    }
    tree_level_trav(ob.insertIntoBST(root, 5));
    return 0;
}

Input

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

Output

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