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

#define MAX_SIZE 100

// Global arrays to store the binary tree
int tree[MAX_SIZE];  // Array to store node values (-1 means empty)
int size = 0;        // Current number of nodes in the tree

// Initialize the binary tree
void initTree() {
    size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        tree[i] = -1;  // -1 indicates empty node
    }
}

// Check if tree is full
int isFull() {
    return size >= MAX_SIZE;
}

// Check if tree is empty
int isEmpty() {
    return size == 0;
}

// Insert root node
void insertRoot(int value) {
    if (isFull()) {
        printf("Tree is full! Cannot insert root.\n");
        return;
    }
    if (tree[0] == -1) {
        tree[0] = value;
        size++;
        printf("Root node %d inserted at index 0\n", value);
    } else {
        printf("Root already exists at index 0 with value %d!\n", tree[0]);
    }
}

// Insert left child at given parent index
void insertLeft(int parentIndex, int value) {
    if (isFull()) {
        printf("Tree is full! Cannot insert left child.\n");
        return;
    }
    
    if (parentIndex >= MAX_SIZE || parentIndex < 0) {
        printf("Invalid parent index!\n");
        return;
    }
    
    if (tree[parentIndex] == -1) {
        printf("Parent node at index %d is empty! Insert parent first.\n", parentIndex);
        return;
    }
    
    int leftChildIndex = 2 * parentIndex + 1;
    if (leftChildIndex >= MAX_SIZE) {
        printf("Cannot insert left child - would exceed array bounds!\n");
        return;
    }
    
    if (tree[leftChildIndex] != -1) {
        printf("Left child already exists at index %d with value %d!\n", 
               leftChildIndex, tree[leftChildIndex]);
        return;
    }
    
    tree[leftChildIndex] = value;
    size++;
    printf("Left child %d inserted at index %d (parent: %d at index %d)\n", 
           value, leftChildIndex, tree[parentIndex], parentIndex);
}

// Insert right child at given parent index
void insertRight(int parentIndex, int value) {
    if (isFull()) {
        printf("Tree is full! Cannot insert right child.\n");
        return;
    }
    
    if (parentIndex >= MAX_SIZE || parentIndex < 0) {
        printf("Invalid parent index!\n");
        return;
    }
    
    if (tree[parentIndex] == -1) {
        printf("Parent node at index %d is empty! Insert parent first.\n", parentIndex);
        return;
    }
    
    int rightChildIndex = 2 * parentIndex + 2;
    if (rightChildIndex >= MAX_SIZE) {
        printf("Cannot insert right child - would exceed array bounds!\n");
        return;
    }
    
    if (tree[rightChildIndex] != -1) {
        printf("Right child already exists at index %d with value %d!\n", 
               rightChildIndex, tree[rightChildIndex]);
        return;
    }
    
    tree[rightChildIndex] = value;
    size++;
    printf("Right child %d inserted at index %d (parent: %d at index %d)\n", 
           value, rightChildIndex, tree[parentIndex], parentIndex);
}

// Get left child index
int getLeftChildIndex(int parentIndex) {
    return 2 * parentIndex + 1;
}

// Get right child index
int getRightChildIndex(int parentIndex) {
    return 2 * parentIndex + 2;
}

// Get parent index
int getParentIndex(int childIndex) {
    if (childIndex <= 0) return -1;
    return (childIndex - 1) / 2;
}

// Get left child value
int getLeftChild(int parentIndex) {
    int leftIndex = getLeftChildIndex(parentIndex);
    if (leftIndex < MAX_SIZE && tree[leftIndex] != -1) {
        return tree[leftIndex];
    }
    return -1;
}

// Get right child value
int getRightChild(int parentIndex) {
    int rightIndex = getRightChildIndex(parentIndex);
    if (rightIndex < MAX_SIZE && tree[rightIndex] != -1) {
        return tree[rightIndex];
    }
    return -1;
}

// Get parent value
int getParent(int childIndex) {
    int parentIndex = getParentIndex(childIndex);
    if (parentIndex >= 0 && tree[parentIndex] != -1) {
        return tree[parentIndex];
    }
    return -1;
}

// Inorder traversal (Left - Root - Right)
void inorderTraversal(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }
    
    inorderTraversal(getLeftChildIndex(index));
    printf("%d ", tree[index]);
    inorderTraversal(getRightChildIndex(index));
}

// Preorder traversal (Root - Left - Right)
void preorderTraversal(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }
    
    printf("%d ", tree[index]);
    preorderTraversal(getLeftChildIndex(index));
    preorderTraversal(getRightChildIndex(index));
}

// Postorder traversal (Left - Right - Root)
void postorderTraversal(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return;
    }
    
    postorderTraversal(getLeftChildIndex(index));
    postorderTraversal(getRightChildIndex(index));
    printf("%d ", tree[index]);
}

// Level order traversal (breadth-first)
void levelOrderTraversal() {
    if (isEmpty()) {
        printf("Tree is empty!\n");
        return;
    }
    
    printf("Level Order Traversal: ");
    for (int i = 0; i < MAX_SIZE; i++) {
        if (tree[i] != -1) {
            printf("%d ", tree[i]);
        }
    }
    printf("\n");
}

// Search for a value in the tree
int search(int value) {
    for (int i = 0; i < MAX_SIZE; i++) {
        if (tree[i] == value) {
            return i;  // Return index if found
        }
    }
    return -1;  // Not found
}

// Get node value at specific index
int getNodeValue(int index) {
    if (index >= 0 && index < MAX_SIZE) {
        return tree[index];
    }
    return -1;
}

// Update node value at specific index
void updateNode(int index, int value) {
    if (index >= 0 && index < MAX_SIZE && tree[index] != -1) {
        printf("Updating node at index %d from %d to %d\n", 
               index, tree[index], value);
        tree[index] = value;
    } else {
        printf("Invalid index or empty node!\n");
    }
}

// Delete a node (set to -1)
void deleteNode(int index) {
    if (index >= 0 && index < MAX_SIZE && tree[index] != -1) {
        printf("Deleting node at index %d with value %d\n", 
               index, tree[index]);
        tree[index] = -1;
        size--;
        
        // Optional: Also delete all children
        printf("Deleting all children of node at index %d as well...\n", index);
        deleteNode(getLeftChildIndex(index));
        deleteNode(getRightChildIndex(index));
    }
}

// Display the entire array representation
void displayTree() {
    printf("\n=== Binary Tree Array Representation ===\n");
    printf("Index: ");
    for (int i = 0; i < MAX_SIZE && i < size * 2; i++) {
        if (tree[i] != -1) {
            printf("%3d ", i);
        }
    }
    printf("\nValue: ");
    for (int i = 0; i < MAX_SIZE && i < size * 2; i++) {
        if (tree[i] != -1) {
            printf("%3d ", tree[i]);
        }
    }
    printf("\n");
    printf("Total nodes: %d\n", size);
    printf("Array size: %d\n", MAX_SIZE);
    printf("=======================================\n");
}

// Display tree in a tree-like format (limited to first few levels)
void displayTreeStructure() {
    printf("\n=== Tree Structure ===\n");
    if (isEmpty()) {
        printf("Tree is empty!\n");
        return;
    }
    
    printf("Level 0: %d\n", tree[0]);
    
    if (tree[1] != -1 || tree[2] != -1) {
        printf("Level 1: ");
        if (tree[1] != -1) printf("%d ", tree[1]);
        else printf("- ");
        if (tree[2] != -1) printf("%d ", tree[2]);
        else printf("-");
        printf("\n");
    }
    
    if (tree[3] != -1 || tree[4] != -1 || tree[5] != -1 || tree[6] != -1) {
        printf("Level 2: ");
        for (int i = 3; i <= 6; i++) {
            if (tree[i] != -1) printf("%d ", tree[i]);
            else printf("- ");
        }
        printf("\n");
    }
    
    if (tree[7] != -1 || tree[8] != -1 || tree[9] != -1 || tree[10] != -1 ||
        tree[11] != -1 || tree[12] != -1 || tree[13] != -1 || tree[14] != -1) {
        printf("Level 3: ");
        for (int i = 7; i <= 14; i++) {
            if (tree[i] != -1) printf("%d ", tree[i]);
            else printf("- ");
        }
        printf("\n");
    }
}

// Calculate height of the tree
int treeHeight(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return 0;
    }
    
    int leftHeight = treeHeight(getLeftChildIndex(index));
    int rightHeight = treeHeight(getRightChildIndex(index));
    
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Count total nodes (wrapper for size)
int countNodes() {
    return size;
}

// Count leaf nodes
int countLeafNodes(int index) {
    if (index >= MAX_SIZE || tree[index] == -1) {
        return 0;
    }
    
    int leftIndex = getLeftChildIndex(index);
    int rightIndex = getRightChildIndex(index);
    
    if ((leftIndex >= MAX_SIZE || tree[leftIndex] == -1) &&
        (rightIndex >= MAX_SIZE || tree[rightIndex] == -1)) {
        return 1;  // This is a leaf node
    }
    
    return countLeafNodes(leftIndex) + countLeafNodes(rightIndex);
}

// Clear the entire tree
void clearTree() {
    initTree();
    printf("Tree has been cleared!\n");
}

// Main function with examples
int main() {
    printf("=== Binary Tree Implementation using Arrays (No Structures/Pointers) ===\n\n");
    
    // Initialize the tree
    initTree();
    
    // Example 1: Creating a simple tree
    printf("Example 1: Creating a simple binary tree\n");
    printf("Tree structure:\n");
    printf("        10\n");
    printf("       /  \\\n");
    printf("      5    15\n");
    printf("     / \\     \\\n");
    printf("    3   7     20\n\n");
    
    insertRoot(10);
    insertLeft(0, 5);
    insertRight(0, 15);
    insertLeft(1, 3);    // Index 1 is node 5
    insertRight(1, 7);   // Index 1 is node 5
    insertRight(2, 20);  // Index 2 is node 15
    
    printf("\n");
    displayTree();
    displayTreeStructure();
    
    printf("\n=== Traversals ===\n");
    printf("Inorder Traversal (Left-Root-Right): ");
    inorderTraversal(0);
    printf("\n");
    
    printf("Preorder Traversal (Root-Left-Right): ");
    preorderTraversal(0);
    printf("\n");
    
    printf("Postorder Traversal (Left-Right-Root): ");
    postorderTraversal(0);
    printf("\n");
    
    levelOrderTraversal();
    
    // Example 2: Searching
    printf("\n=== Searching ===\n");
    int searchValue = 7;
    int index = search(searchValue);
    if (index != -1) {
        printf("Value %d found at index %d\n", searchValue, index);
        printf("  - Parent value: %d at index %d\n", 
               getParent(index), getParentIndex(index));
        printf("  - Left child: %d at index %d\n", 
               getLeftChild(index), getLeftChildIndex(index));
        printf("  - Right child: %d at index %d\n", 
               getRightChild(index), getRightChildIndex(index));
    } else {
        printf("Value %d not found in tree\n", searchValue);
    }
    
    // Example 3: Tree properties
    printf("\n=== Tree Properties ===\n");
    printf("Tree height: %d\n", treeHeight(0));
    printf("Total nodes: %d\n", countNodes());
    printf("Leaf nodes: %d\n", countLeafNodes(0));
    
    // Example 4: Updating a node
    printf("\n=== Updating Node ===\n");
    updateNode(3, 8);  // Update node at index 3 from 3 to 8
    displayTree();
    
    // Example 5: Array index calculations
    printf("\n=== Array Index Calculation Demonstration ===\n");
    printf("For root node at index 0 (value: %d):\n", tree[0]);
    printf("  - Left child index: %d\n", getLeftChildIndex(0));
    printf("  - Right child index: %d\n", getRightChildIndex(0));
    printf("For node at index 2 (value: %d):\n", tree[2]);
    printf("  - Parent index: %d\n", getParentIndex(2));
    printf("  - Left child index: %d\n", getLeftChildIndex(2));
    printf("  - Right child index: %d\n", getRightChildIndex(2));
    
    // Example 6: Creating a complete binary tree
    printf("\n=== Example 2: Creating a complete binary tree ===\n");
    initTree();  // Reset tree
    
    printf("Creating a complete binary tree with values 1-7\n");
    printf("Structure:\n");
    printf("        1\n");
    printf("       / \\\n");
    printf("      2   3\n");
    printf("     / \\ / \\\n");
    printf("    4  5 6  7\n\n");
    
    int values[] = {1, 2, 3, 4, 5, 6, 7};
    insertRoot(values[0]);
    insertLeft(0, values[1]);
    insertRight(0, values[2]);
    insertLeft(1, values[3]);
    insertRight(1, values[4]);
    insertLeft(2, values[5]);
    insertRight(2, values[6]);
    
    printf("\nComplete Binary Tree Traversal:\n");
    printf("Inorder: ");
    inorderTraversal(0);
    printf("\nPreorder: ");
    preorderTraversal(0);
    printf("\nPostorder: ");
    postorderTraversal(0);
    printf("\n");
    levelOrderTraversal();
    
    printf("\nTree height: %d\n", treeHeight(0));
    printf("Number of leaf nodes: %d\n", countLeafNodes(0));
    
    // Example 7: Search in complete tree
    printf("\n=== Searching in Complete Tree ===\n");
    searchValue = 5;
    index = search(searchValue);
    if (index != -1) {
        printf("Found %d at index %d\n", searchValue, index);
        printf("Parent of %d is %d at index %d\n", 
               searchValue, getParent(index), getParentIndex(index));
    }
    
    // Example 8: Demonstration of array indices for sparse tree
    printf("\n=== Example 3: Creating a skewed tree ===\n");
    initTree();
    printf("Creating a right-skewed tree:\n");
    printf("10 -> 20 -> 30 -> 40\n\n");
    
    insertRoot(10);
    insertRight(0, 20);   // node 20 at index 2
    insertRight(2, 30);   // right child of index 2 → index 6
    insertRight(6, 40);   // right child of index 6 → index 14
    
    displayTree();
    printf("Inorder traversal of skewed tree: ");
    inorderTraversal(0);
    printf("\n");
    
    printf("\n=== Array Index Analysis for Skewed Tree ===\n");
    printf("Node 10 at index 0\n");
    printf("Node 20 at index 2 (right child of 0)\n");
    printf("Node 30 at index 6 (right child of index 2)\n");
    printf("Node 40 at index 14 (right child of index 6)\n");
    printf("Notice the exponential growth in indices!\n");
    
    return 0;
}