Deleting, and Why Balance Matters

Deleting: three cases

• No children: just remove it.
• One child: replace the node with its child.
• Two children: copy in the next bigger value (smallest in the right subtree), then delete that value from the right subtree.

#include <algorithm>
#include <iostream>
using namespace std;

struct Node {
    int value;
    Node *left, *right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* r, int v) {
    if (!r) return new Node(v);
    if (v < r->value) r->left = insert(r->left, v);
    else r->right = insert(r->right, v);
    return r;
}

Node* erase(Node* r, int v) {
    if (!r) return nullptr;
    if (v < r->value) r->left = erase(r->left, v);
    else if (v > r->value) r->right = erase(r->right, v);
    else {
        if (!r->left) { Node* keep = r->right; delete r; return keep; }
        if (!r->right) { Node* keep = r->left; delete r; return keep; }
        Node* next = r->right;
        while (next->left) next = next->left;
        r->value = next->value;
        r->right = erase(r->right, next->value);
    }
    return r;
}

int height(Node* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }
void inorder(Node* n) { if (!n) return; inorder(n->left); cout << n->value << ' '; inorder(n->right); }

int main() {
    Node* root = nullptr;
    for (int v : {50, 30, 70, 20, 40, 60, 80}) root = insert(root, v);
    for (int v : {20, 30, 50}) {
        root = erase(root, v);
        cout << "after deleting " << v << ": ";
        inorder(root);
        cout << " (root " << root->value << ")" << endl;
    }

    Node* mixed = nullptr;
    Node* line = nullptr;
    for (int v : {8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15}) mixed = insert(mixed, v);
    for (int v = 1; v <= 15; v++) line = insert(line, v);
    cout << "mixed order height " << height(mixed) << ", sorted order height " << height(line) << endl;
    return 0;
}

Output

after deleting 20: 30 40 50 60 70 80  (root 50)
after deleting 30: 40 50 60 70 80  (root 50)
after deleting 50: 40 60 70 80  (root 60)
mixed order height 4, sorted order height 15

Inserting sorted values makes every node go right: a long line of height n, so searching becomes O(n).