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(Node** leaves, int n) {
    if (n == 1) {
        return leaves[0];
    }

    int new_n = (n + 1) / 2;
    Node** new_leaves = (Node**)malloc(new_n * sizeof(Node*));

    for (int i = 0; i < new_n; i++) {
        if (2 * i + 1 < n) {
            unsigned int combined_hash = merge_and_hash(leaves[2 * i]->data, leaves[2 * i + 1]->data);
            Node* parent = create_tree_node(combined_hash);
            parent->left = leaves[2 * i];
            parent->right = leaves[2 * i + 1];
            new_leaves[i] = parent;
        } else {
            unsigned int adjusted_hash = merge_and_hash(leaves[2 * i]->data, leaves[2 * i]->data);
            Node* parent = create_tree_node(adjusted_hash);
            parent->left = leaves[2 * i];
            new_leaves[i] = parent;
        }
    }

    Node* root = build_merkle_tree(new_leaves, new_n);
    free(new_leaves);

    return root;
}

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

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

    while (count > 0) {
        int next_count = 0;
        Node** next_level = (Node**)malloc(2 * count * sizeof(Node*));

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

        free(current_level);
        current_level = next_level;
        count = next_count;
    }

    free(current_level);
}

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

    char **strings = (char **)malloc(n * sizeof(char *));
    Node **leaves = (Node **)malloc(n * sizeof(Node *));
    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]);
        leaves[i] = create_tree_node(hashes[i]);
    }

    Node *root = build_merkle_tree(leaves, n);

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

    free(leaves);
    free(hashes);

    return 0;
}