// Binary tree — linked representation (struct + left/right pointers).
// Same example shapes as binary-tree-array-demo.c for easy comparison.
// Compile: gcc -std=c11 binary-tree-linkedlist-demo.c -o tree_ll_demo

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

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

// ---------- Memory helpers ----------

Node *createNode(int data) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (n == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->left = n->right = NULL;
    return n;
}

// Post-order free: safe for arbitrary binary tree
void freeTree(Node *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// ---------- Metrics ----------

int treeHeight(Node *root) {
    if (root == NULL) {
        return 0;
    }
    int lh = treeHeight(root->left);
    int rh = treeHeight(root->right);
    return (lh > rh ? lh : rh) + 1;
}

int countNodes(Node *root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int countLeaves(Node *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}

Node *search(Node *root, int value) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == value) {
        return root;
    }
    Node *t = search(root->left, value);
    if (t != NULL) {
        return t;
    }
    return search(root->right, value);
}

// ---------- Depth-first traversals ----------

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

void preorder(Node *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void postorder(Node *root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

// Level order: array-based queue of Node * (simple, fixed cap)

#define QUEUE_CAP 512

void levelOrder(Node *root) {
    if (root == NULL) {
        printf("(empty tree)\n");
        return;
    }
    Node *q[QUEUE_CAP];
    int front = 0, rear = 0;
    q[rear++] = root;
    while (front < rear) {
        Node *cur = q[front++];
        printf("%d ", cur->data);
        if (cur->left != NULL) {
            q[rear++] = cur->left;
        }
        if (cur->right != NULL) {
            q[rear++] = cur->right;
        }
    }
}

// Build the “textbook” example tree (same as array demo):
// root 10; children 5 (left), 15 (right); 3,7 under 5; 20 under 15 (right).

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

// Complete tree with values 1..7 (full last level).

Node *buildCompleteTree(void) {
    Node *r = createNode(1);
    r->left = createNode(2);
    r->right = createNode(3);
    r->left->left = createNode(4);
    r->left->right = createNode(5);
    r->right->left = createNode(6);
    r->right->right = createNode(7);
    return r;
}

// Right-skewed chain 10 -> 20 -> 30 -> 40 (only right pointers)

Node *buildSkewedRight(void) {
    Node *r = createNode(10);
    r->right = createNode(20);
    r->right->right = createNode(30);
    r->right->right->right = createNode(40);
    return r;
}

// ---------- Main demos ----------

int main(void) {
    printf("=== Binary tree (linked list / pointer representation) ===\n\n");

    printf("Example 1: sample tree (same logical shape as array demo)\n");
    Node *t1 = buildExampleTree();
    printf("Inorder:    ");
    inorder(t1);
    printf("\nPreorder:   ");
    preorder(t1);
    printf("\nPostorder:  ");
    postorder(t1);
    printf("\nLevel order:");
    levelOrder(t1);
    printf("\n");

    printf("Height: %d | Nodes: %d | Leaves: %d\n",
           treeHeight(t1), countNodes(t1), countLeaves(t1));

    Node *hit = search(t1, 7);
    if (hit != NULL) {
        printf("Found value 7 at node %p (data=%d)\n", (void *)hit, hit->data);
    }

    printf("\nExample 2: complete binary tree (values 1..7)\n");
    freeTree(t1);
    Node *t2 = buildCompleteTree();
    printf("Level order: ");
    levelOrder(t2);
    printf("\nHeight: %d | Leaves: %d\n", treeHeight(t2), countLeaves(t2));
    freeTree(t2);

    printf("\nExample 3: right-skewed chain — no wasted array slots\n");
    Node *t3 = buildSkewedRight();
    printf("Inorder (chain): ");
    inorder(t3);
    printf("\nNodes: %d | Height: %d\n", countNodes(t3), treeHeight(t3));
    freeTree(t3);

    printf("\nDone.\n");
    return 0;
}