SortedBinaryRemoveNode.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define EMPTY NULL
#define ARR_SIZE 10

struct btree {
    int data;
    struct btree *left;
    struct btree *right;
};

struct btree* add(struct btree * bt, int data) {
    if (bt) {
        if (bt->data < data) {
            bt->left = add(bt->left, data);
            return bt;
        }else if (bt->data > data) {
            bt->right = add(bt->right, data);
            return bt;
        }else {
            return bt;
        }
    }else {
        struct btree * ans = (struct btree*)malloc(sizeof(struct btree));
        if (!ans) {
            fputs("alocation failed!\n", stderr);
            exit(1);
        }
        ans->data = data;
        ans->left = EMPTY;
        ans->right = EMPTY;
        return ans;
    }
}

void display(const struct btree * bt) {
    if (bt) {
        display(bt->left);
        fprintf(stdout, "%d\n", bt->data);
        display(bt->right);
    }else {
        fputs("EMPTY\n", stdout);
    }
}

const struct btree* find(const struct btree * bt, const int data) {
    if (bt) {
        if (bt->data < data) {
            return find(bt->left, data);
        }else if (bt->data > data) {
            return find(bt->right, data);
        }else {
            return bt;
        }
    }else {
        return bt;
    }
}

void freeBtree(struct btree * bt) {
    if (bt) {
        freeBtree(bt->left);
        freeBtree(bt->right);
        free(bt);
    }
}

struct btree* joinBranches(struct btree * left, struct btree * right) {
    if (!left) {
        return right;
    }else if (!right) {
        return left;
    }else {
        if (!right->left) {
            right->left = left;
            return right;
        }else {
            joinBranches(left, right->left);
            return right;
        }
    }
}

void removeNodeAux(struct btree ** bt, struct btree ** prev, bool left, const int data) {
    if (*bt) {
        if ((*bt)->data < data) {
            removeNodeAux(&(*bt)->left, bt, true, data);
        }else if ((*bt)->data > data) {
            removeNodeAux(&(*bt)->right, bt, false, data);
        }else {
            if (*prev) {
                struct btree * l = (*bt)->left;
                struct btree * r = (*bt)->right;
                free(*bt);
                if (left) {
                    (*prev)->left = joinBranches(l, r);
                }else {
                    (*prev)->right = joinBranches(l, r);
                }
            }else {
                struct btree * l = (*bt)->left;
                struct btree * r = (*bt)->right;
                free(*bt);
                (*bt) = joinBranches(l, r);
            }
        }
    }
}

void removeNode(struct btree ** bt, const int data) {
    struct btree *prev = EMPTY;
    removeNodeAux(bt, &prev, false, data);
}

int main (int argc, char ** argv) {
    int data[ARR_SIZE] = {10, 1, 8, 2, 3, 9, 7, 5, 6, 4};
    struct btree * bt = EMPTY;
    size_t i = 0;

    for (; i < ARR_SIZE; i++) {
        bt = add(bt, data[i]);
    }

    display(bt);

    removeNode(&bt, 5);

    fputs("\n\n", stdout);

    display(bt);

    freeBtree(bt);

    return 0;
}