void enqueue(queue *q, treenode *item){
    node *new_node = (node *)malloc(sizeof(node));

    if(new_node == NULL){
        printf("memory overflow\n");
        exit(1);
    }

    new_node->element = item;
    new_node->next = NULL;

    if(is_empty_queue(q)){
        q->front = new_node;
        q->rear = new_node;
    }else{
    //  if(((*new_node).element)<((*new_node->next).element))



        (q->rear)->next = new_node;
        q->rear = new_node;
    }

    q->size++;
}

treenode *dequeue(queue *q){
    node *temp;                                     /*reference to the to-be dequeued node*/
    treenode *result;

    if(is_empty_queue(q)){
        printf("Queue underflow\n");
        exit(1);
    }

    temp = q->front;
    q->front = (q->front)->next;

    if(q->front == NULL){
        q->rear = NULL;
    }
    q->size--;

    result = temp->element;
    free(temp);

    return result;
}


void *construct(struct arrange arr[], int length){
    int i;
    int n;
    queue q;
    treenode *temp;
    treenode *x, *y, *z;
    init_queue(&q);
    printf("\nenqueue ");
    /*wrap the elements to treenodes and insert them to the queue*/
    for(i = 0; i < length; i++){
        temp = (treenode *)malloc(sizeof(treenode));
        if(temp == NULL){
            printf("Memory overflow\n");
            exit(1);
        }
        temp->element = arr[i].freq;
        temp->left = NULL;
        temp->right = NULL;
        printf("%d ", temp->element);
        enqueue(&q,temp);
    }
    printf("\ndequeue ");
    n = q.size;
    for(i = 0; i < n - 1; i++){
        x = dequeue(&q);
        y = dequeue(&q);
        z = (treenode *)malloc(sizeof(node));
        if(z == NULL){
            printf("memory overflow");
            exit(1);
        }
        z->element = x->element + y->element;
        z->left = x;
        z->right = y;
        printf("%d ",z->element);
        enqueue(&q,z);
    /*  enqueue a treenode*/
    }

    return dequeue(&q);
}