Рекурсия при заполнении бинарного дерева - C (СИ)

Формулировка задачи:

Есть список с элементами, которые заносятся в дерево по прямому ходу.

struct tree *ForwardStroke(struct List *U, int sizeTree)
{
    struct tree *cur=(struct tree*)malloc(sizeof(struct tree));
    cur->left=cur->right=NULL;
    cur->info=U->n;
    U=U->next;
    if(sizeTree>1 && U!=NULL)
    {
        cur->left=ForwardStroke(U, sizeTree-1);
        cur->right=ForwardStroke(U, sizeTree-1);
    }
    return cur;
}

Эта функция построения дерева. Она, конечно же, неправильная и глупая. Сначала заполняется левое поддерево до нужного уровня, затем возвращается на этаж выше в дерево, чтобы заполнить правое поддерево, но при этом список тоже возвращается. Т.е получается левое поддерево корня, как на картинке. Но это неправильно. Как исправить функцию, чтобы список не возвращался в положение, которое было до очередного входа в функцию??

Решение задачи: «Рекурсия при заполнении бинарного дерева»

Листинг программы

int Add(Element *curr, int value)
{
  if(!curr){  //Если указатель нулевой, то создание корня
    //Выделение памяти под элемент
    root = (Element *)malloc(sizeof(Element));
    if(!root) return 1; //Если память не выделилась - выход
    root->parent = NULL;//Инициализация связи с родителем
    //Инициализация связи с потомками
    root->left = root->right = NULL;
    root->value = value;  //Запись значения
  }else{ //Иначе: не корневой элемент
    //Если значение больше значения текущего элемента
    if(curr->value < value){
      //Если присутствует дочерний элемент слева, то
      //вызов функции добавления к дочернему элементу
      if(curr->left) return Add(curr->left,value);
    }else{ //иначе: если меньше или равно
      //Если присутствует дочерний элемент справа, то
      //вызов функции добавления к дочернему элементу
      if(curr->right) return Add(curr->right,value);
    }
    //Выделение памяти под новый элемент
    Element *tmp = (Element*)malloc(sizeof(Element));
    if(!tmp) return 1; //Если память не выделилась - выход
    //Инициализация связей с дочерними элементами
    tmp->right = tmp->left = NULL;
    //Установка связи с родительским элементом
    tmp->parent = curr;
    tmp->value = value; //Запись значения
    //Если значение нового элемента больше, чем значение
    //текущего элемента,  то добавление  в  левую  ветвь.
    //В противном случае - в правую
    if(curr->value < value) curr->left = tmp;
      else curr->right = tmp;
  }
  return 0; //Успешное завершение
}

Объяснение кода листинга программы

Функция Add принимает два аргумента: указатель на текущий элемент curr и значение value для добавления.
Если curr равен NULL, то это означает, что мы добавляем элемент в пустое дерево, поэтому мы выделяем память под новый корень root и инициализируем его связи с родителем и потомками (путем вызова функции malloc и присвоения NULL значений left и right). Значение value записывается в root->value.
Если curr не равен NULL, то мы проверяем, больше ли value значения текущего элемента curr.
Если value больше, мы вызываем рекурсивно функцию Add для левого поддерева (передаем curr->left и value в качестве аргументов). Если левое поддерево не пустое, то мы продолжаем рекурсивный вызов для правого поддерева.
Если value меньше или равно curr->value, мы вызываем рекурсивно функцию Add для правого поддерева (передаем curr->right и value в качестве аргументов). Если правое поддерево не пустое, то мы продолжаем рекурсивный вызов для левого поддерева.
Если оба поддерева пустые, то мы выделяем память под новый элемент tmp и инициализируем его связи с родительским элементом curr и дочерними элементами (путем вызова функции malloc и присвоения NULL значений left и right). Значение value записывается в tmp->value.
Мы добавляем tmp в левое или правое поддерево в зависимости от того, больше ли value значения curr.
В конце функция возвращает 0, что означает успешное завершение. Если в процессе выделения памяти происходит ошибка, функция возвращает 1.