Untitled

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

// MurmurOAAT32 hash function
unsigned int MurmurOAAT32(char *key) {
    unsigned int h = 3323198485u;
    for (; *key; ++key) {
        h ^= *key;
        h *= 0x5bd1e995;
        h ^= h >> 15;
    }
    return h;
}

// Function to convert unsigned int to string
void unsigned_int_to_string(unsigned int num, char *str) {
    sprintf(str, "%u", num);
}

// Function to merge and hash two values in the binary tree
unsigned int merge_and_hash(unsigned int a, unsigned int b) {
    unsigned int sum = a + b;
    char buffer[11]; // enough to hold a 32-bit unsigned int
    unsigned_int_to_string(sum, buffer);
    return MurmurOAAT32(buffer);
}

// Definition of tree node
typedef struct Node {
    unsigned int data;
    struct Node *left;
    struct Node *right;
} Node;

// Function to create a new tree node
Node* create_tree_node(unsigned int data) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

// Recursive function to build the Merkle tree and collect hash values
Node* build_merkle_tree(unsigned int *hashes, int n) {
    if (n == 1) {
        return create_tree_node(hashes[0]);
    }

    int new_n = (n + 1) / 2;
    unsigned int *new_hashes = (unsigned int *)malloc(new_n * sizeof(unsigned int));
    Node **nodes = (Node **)malloc(n * sizeof(Node*));

    for (int i = 0; i < n; i++) {
        nodes[i] = create_tree_node(hashes[i]);
    }

    for (int i = 0; i < new_n; i++) {
        if (2 * i + 1 < n) {
            new_hashes[i] = merge_and_hash(hashes[2 * i], hashes[2 * i + 1]);
            Node *parent = create_tree_node(new_hashes[i]);
            parent->left = nodes[2 * i];
            parent->right = nodes[2 * i + 1];
            nodes[i] = parent;
        } else {
            char buffer[11];
            unsigned_int_to_string(hashes[2 * i] * 2, buffer);
            new_hashes[i] = MurmurOAAT32(buffer);
            nodes[i] = create_tree_node(new_hashes[i]);
            nodes[i]->left = nodes[2 * i];
        }
    }

    Node *root = build_merkle_tree(new_hashes, new_n);
    free(new_hashes);
    free(nodes);

    return root;
}

// Function to print the Merkle tree by level
void print_merkle_tree(Node* root) {
    if (!root) return;

    Node** currentLevel = (Node**)malloc(sizeof(Node*));
    currentLevel[0] = root;
    int count = 1;

    while (count > 0) {
        int nextCount = 0;
        Node** nextLevel = (Node**)malloc(2 * count * sizeof(Node*));

        for (int i = 0; i < count; i++) {
            printf("%-15u", currentLevel[i]->data);
            if (currentLevel[i]->left) {
                nextLevel[nextCount++] = currentLevel[i]->left;
            }
            if (currentLevel[i]->right) {
                nextLevel[nextCount++] = currentLevel[i]->right;
            }
        }
        printf("\n");

        free(currentLevel);
        currentLevel = nextLevel;
        count = nextCount;
    }

    free(currentLevel);
}

int main() {
    int n;
    scanf("%d", &n);

    char **strings = (char **)malloc(n * sizeof(char *));
    unsigned int *hashes = (unsigned int *)malloc(n * sizeof(unsigned int));

    for (int i = 0; i < n; i++) {
        strings[i] = (char *)malloc(101 * sizeof(char)); // 100 chars + null terminator
        scanf("%s", strings[i]);
        hashes[i] = MurmurOAAT32(strings[i]);
    }

    Node *root = build_merkle_tree(hashes, n);

    // Print the last layer (all leaves)
    for (int i = 0; i < n; i++) {
        printf("%-15u", hashes[i]);
    }
    printf("\n");

    // Print the Merkle tree by level
    print_merkle_tree(root);

    for (int i = 0; i < n; i++) {
        free(strings[i]);
    }
    free(strings);
    free(hashes);

    return 0;
}