Изменение связанного списка, чтобы превратить его в двоичное дерево

Question

Вот формат структуры, используемой для создания связанного списка:

struct LetterFrequencyPair
{
    char character;
    int frequency;
    struct LetterFrequencyPair* next;
};

/ ********************************************** ********************************** \

void createList()
{
    char c;
    int f;
    struct LetterFrequencyPair* temp;

    temp = malloc(sizeof(struct LetterFrequencyPair));
    printf("Enter the Character: ");
    scanf("%c", &c);
    temp->character = c;
    printf("Enter the frequency of the character: ");
    scanf("%d", &f);
    getchar();
    temp->frequency = f;
    temp->next = NULL;

    if (root == NULL)
    {
        root = temp;
    }
    else
    {
        struct LetterFrequencyPair* p;
        p = root;

        while (p->next != NULL)
        {
            p = p->next;
        }
        p->next = temp;     
    }
    printf("\n");
}

Выше я написал функцию для создания связанного списка.

Мой вопрос: как я могу изменить эту функцию и структуру, чтобы вместо этого генерировать двоичное дерево?

Я знаю, что мне придется изменить структуру, чтобы указатели указывали на левого и правого потомка, а не на следующий. Но я застреваю при попытке связать все это, поскольку есть два разных направления. Я вставил мою попытку изменения ниже:

struct LetterFrequencyPair
{
    char character;
    int frequency;
    //Creating a pointer to point to the next child in the list
    struct BinaryTreeNode* leftChild;
    struct BinaryTreeNode* rightChild;
};

 void createList()
 {
    char c;
    int f;
    struct LetterFrequencyPair* temp;

    temp = malloc(sizeof(struct LetterFrequencyPair));
    printf("Enter the Character: ");
    scanf("%c", &c);
    temp->character = c;
    printf("Enter the frequency of the character: ");
    scanf("%d", &f);
    getchar();
    temp->frequency = f;
    temp->leftChild = NULL;
    temp->rightChild = NULL;

    if ((rootRight = NULL) && (rootLeft = NULL))
    {
        root = temp;
    }
    else
    {
        struct LetterFrequencyPair* p;
        p = root;

        while (p->leftChild != NULL)
        {
            p = p->leftChild;
        }
        p->leftChild = temp;

        struct LetterFrequencyPair * p1;
        p1 = root;

        while (p1->rightChild != NULL)
        {
            p1 = p1 ->rightChild;
        }
            p1->rightChild = temp;
    }

printf("\n");
}