binary_search_tree.cpp

struct Node {
    int value;
    Node *left;
    Node *right;
};

struct Tree {
    Node *root;
};

void insert_helper(Node *root, int value) {
    if (root) {
        if (root->value > value) {
            if (root->left) {
                insert_helper(root->left, value);
            } else {
                Node *n = new Node;
                n->value = value;
                n->left = NULL;
                n->right = NULL;
                root->left = n;
            }
        } else if (root->value < value){
            if (root->right) {
                insert_helper(root->right, value);
            } else {
                Node *n = new Node;
                n->value = value;
                n->left = NULL;
                n->right = NULL;
                root->right = n;
            }
        } else {
            // do nothing, value exists
            return;
        }
    }
}

void insert(Tree *tree, int value) {

    // Case 1: tree is empty
    if (!tree->root) {
        Node *n = new Node;
        n->value = value;
        n->left = NULL;
        n->right = NULL;
        tree->root = n;
        return;
    }

    // Case 2: Tree is non-empty
    insert_helper(tree->root, value);
}

Node* getMin(Node *root) {

    if (root) {
        if (root->left) {
            return getMin(root->left);
        } else {
            return root;
        }
    } else {
        // Shouldn't happen
        return NULL;
    }
}

Node *delete_helper(Node *root, int value) {

    if (root) {
        if (root->value == value) {
            // Case 1: root has no children
            if (!root->left && !root->right) {
                Node *tmp = root;
                root = NULL;
                delete tmp;
                return root;
            }
            // Case 2: root has 1 child
            if (!root->left && root->right) {
                Node *tmp = root;
                root = root->right;
                delete tmp;
                return root;
            }
            if (!root->right && root->left) {
                Node *tmp = root;
                root = root->left;
                delete tmp;
                return root;
            }
            // Case 3: root has 2 children
            // Replace root with highest value smaller than root
            Node *minRight = getMin(root->right);
            root->value = minRight->value;
            // Now delete minRight node; set its parent's left child to NULL or
            // to minRight node's right child
            root->right = delete_helper(root->right, minRight->value);
        }
        else if (root->value > value) {
            // Delete value node from left sub-tree
            root->left = delete_helper(root->left, value);
        } else {
            // Delete value node from right sub-tree
            root->right = delete_helper(root->right, value);
        }
    } else {
        // Nothing to delete
        return root;
    }
}

void delete(Tree *tree, int value) {

    // Case 1: tree is empty
    if (!tree->root)
        return;

    // Case 2: Tree is non-empty
    tree->root = delete_helper(tree->root, value);
}