// Binary tree operations demo (linked representation).
// Covers search, attach child under a known parent value, delete by value (3 cases).
// Duplicate values are not supported as keys (delete removes one occurrence predictably via DFS order).
// Compile: gcc -std=c11 binary-tree-operations-demo.c -o tree_ops_demo

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

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

static Node *createNode(int data) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->left = n->right = NULL;
    return n;
}

static void freeTree(Node *root) {
    if (!root) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// DFS search first matching value
Node *find(Node *root, int value) {
    if (!root) {
        return NULL;
    }
    if (root->data == value) {
        return root;
    }
    Node *t = find(root->left, value);
    return t ? t : find(root->right, value);
}

static void inorder(Node *root) {
    if (!root) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

static Node *maxRightmostInSubtree(Node *sub) {
    if (!sub) {
        return NULL;
    }
    Node *cur = sub;
    while (cur->right) {
        cur = cur->right;
    }
    return cur;
}

// Remove first node with key found in subtree rooted at root; returns new subtree root.
static Node *deleteFound(Node *root);

Node *deleteByValue(Node *root, int key) {
    if (!root) {
        return NULL;
    }
    if (root->data == key) {
        return deleteFound(root);
    }
    root->left = deleteByValue(root->left, key);
    root->right = deleteByValue(root->right, key);
    return root;
}

static Node *deleteFound(Node *root) {
    if (!root->left && !root->right) {
        free(root);
        return NULL;
    }
    if (!root->left) {
        Node *t = root->right;
        free(root);
        return t;
    }
    if (!root->right) {
        Node *t = root->left;
        free(root);
        return t;
    }
    // Two children: replace with value from rightmost node in left subtree, then delete that node.
    Node *pred = maxRightmostInSubtree(root->left);
    root->data = pred->data;
    root->left = deleteByValue(root->left, pred->data);
    return root;
}

bool attachLeft(Node *root, int parentValue, int newValue) {
    Node *p = find(root, parentValue);
    if (!p || p->left) {
        return false;
    }
    p->left = createNode(newValue);
    return true;
}

bool attachRight(Node *root, int parentValue, int newValue) {
    Node *p = find(root, parentValue);
    if (!p || p->right) {
        return false;
    }
    p->right = createNode(newValue);
    return true;
}

// Build sample tree: root 10; children 5,15; leaves 3,7 and 20 under 15.

static Node *buildSample(void) {
    Node *r = createNode(10);
    r->left = createNode(5);
    r->right = createNode(15);
    r->left->left = createNode(3);
    r->left->right = createNode(7);
    r->right->right = createNode(20);
    return r;
}

int main(void) {
    printf("=== Binary tree operations (linked) ===\n\n");

    Node *root = buildSample();
    printf("Initial inorder: ");
    inorder(root);
    printf("\n");

    printf("\n-- Search --\n");
    int keys[] = {7, 99};
    for (size_t i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
        Node *h = find(root, keys[i]);
        printf("find(%d): %s\n", keys[i], h ? "found" : "not found");
    }

    printf("\n-- Attach child (only if slot empty) --\n");
    if (attachLeft(root, 15, 12)) {
        printf("Attached 12 as left child of 15\n");
    } else {
        printf("attachLeft(15,12) failed (missing parent or left busy)\n");
    }
    printf("Inorder after attach: ");
    inorder(root);
    printf("\n");

    printf("\n-- Delete leaf (20) --\n");
    root = deleteByValue(root, 20);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\n-- Delete one-child node (15 has only left child 12; delete 15 lifts 12 to parent) --\n");
    root = deleteByValue(root, 15);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\n-- Delete node with two children (root 10) --\n");
    printf("Before: ");
    inorder(root);
    printf("\n");
    root = deleteByValue(root, 10);
    printf("After removing 10: ");
    inorder(root);
    printf("\n");

    printf("\nFreeing remaining tree...\n");
    freeTree(root);
    printf("Done.\n");
    return 0;
}