Editing Binary Search Trees (section)

== Operations ==

The main operations on a binary search tree are insertion, deletion, and search.

=== Insertion ===

To insert a new value into a BST, we start at the root and compare the new value to the value of the current node. If the new value is less than the current node's value, we move to the left subtree; otherwise, we move to the right subtree. We repeat this process until we reach a null pointer, where we create a new node with the new value and insert it.

Example:

<pre>
Node* insert(Node* root, int value) {
    if (root == nullptr) {
        return new Node(value);
    }

    if (value < root->data) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}
</pre>

=== Deletion ===

To delete a value from a BST, we first search for the node containing the value. If the node has no children, we simply remove it. If the node has one child, we replace the node with its child. If the node has two children, we find the inorder successor (or predecessor) of the node, replace the node with the successor, and then delete the successor.

Example:

<pre>
Node* minValueNode(Node* node) {
    Node* current = node;

    while (current && current->left) {
        current = current->left;
    }

    return current;
}

Node* deleteNode(Node* root, int value) {
    if (root == nullptr) {
        return root;
    }

    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }

        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}
</pre>

=== Search ===

To search for a value in a BST, we start at the root and compare the target value to the value of the current node. If the target value is less than the current node's value, we move to the left subtree; otherwise, we move to the right subtree. We repeat this process until we find the target value or reach a null pointer.

Example:

<pre>
bool search(Node* root, int value) {
    if (root == nullptr) {
        return false;
    }

    if (root->data == value) {
        return true;
    }

    if (value < root->data) {
        return search(root->left, value);
    } else {
        return search(root->right, value);
    }
}
</pre>