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

struct tree{
    int x;
    struct tree* left;
    struct tree* right;
};

int search(struct tree* root, int key) {
    if (root == NULL)
        return 0;
    if (key == root->x)
        return 1;
    if (key > root->x)
        return search(root->right, key);
    else
        return search(root->left, key);
}

struct tree* insert(struct tree* root, int key) {
    if (root == NULL) {
        struct tree* node = (struct tree*)malloc(sizeof(struct tree));
        node->x = key;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (key > root->x)
        root->right = insert(root->right, key);
    else
        root->left = insert(root->left, key);
    return root;
}

int min(struct tree* root) {
    if (root->left != NULL)
        return min(root->left);
    else
        return root->x;
}

struct tree* delete(struct tree* root, int key) {
    if (root == NULL)
        return root;
    if (key < root->x)
        root->left = delete(root->left, key);
    else if (key > root->x)
        root->right = delete(root->right, key);
    else if (root->left != NULL && root->right != NULL) {
        root->x = min(root->right);
        root->right = delete(root->right, root->x);
    }
    else {
        if (root->left != NULL)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

void print(struct tree* root) {
    if (root == NULL)
        return;
    print(root->left);
    printf("%d ", root->x);
    print(root->right);
}

int main() {


    //struct listNode* nd = (struct listNode*)malloc(size + 1);

    struct tree* root = NULL;

    root = insert(root, 1);
    root = insert(root, 2);
    root = insert(root, 3);
    root = insert(root, 4);
    print(root);
    printf("\n");
    root = delete(root, 3);
    print(root);


    return 0;
}