int delete(Tree* root, Item x) {
    if (!*root) {
        return 0;
    }
    bnode* n = searchInTree(*root, x);

    // node does not have two children
    if (!(n->right && n->left)) {
        if (n->parent->right == n) {
            n->parent->right = (bnode*)((long)n->left | (long)n->right);
        }
        else {
            n->parent->left = (bnode*)((long)n->left | (long)n->right);
        }
        free(n);
        return 1;
    }

    Item maxKey = (max(n->left))->key;
    if (!delete(&(n->left), maxKey)) {
        return 0;
    }
    n->key = maxKey;
    return 1;
}