Ошибка при вставке элемента в двоичное дерево поиска

Question

Программа создает двоичное дерево поиска из отсортированного массива чисел и добавляет к нему элементы.

struct Tree 
{ 
    Tree *left_son, *right_son; 
    int head, key; 
}; 

Tree *tree(int *a, int left, int right) 
{ 
    Tree *tree1 = new Tree; 
    int mid = middle(left,right); 
    tree1->head = a[mid]; 
    if (left != mid) 
    { 
     tree1->left_son = tree(a, left, mid-1); 
    } 
    if (right != mid) 
    { 
     tree1->right_son = tree(a, mid+1, right); 
    } 
    return tree1; 
} 
void add (Tree * curr_pos, int key) 
{ 
    if (key < curr_pos->head) 
    { 
     if (curr_pos->left_son != nullptr) 
      add (curr_pos->left_son, key); 
     else 
     { 
      Tree * tmp_tree = new Tree; 
      curr_pos->left_son = tmp_tree; 
     } 
    } 
    else 
    { 
     if (curr_pos->right_son != nullptr) 
      add (curr_pos->right_son, key); 
     else 
     { 
      Tree * tmp_tree = new Tree; 
      curr_pos->right_son = tmp_tree; 
     } 
    } 
} 

Проблема заключается в линии if (curr_pos->left_son != nullptr) , когда узел не имеет левого «сына», удовлетворяет условию по какой-то причине, но он не должен. Я имею в виду, что программа находит оставшегося «сына», даже если его нет, и указатель перемещается туда. Извините, мой английский плохой, но я надеюсь, что кто-то может понять, что я сказал.

Answer 1

Tree *tree(int *a, int left, int right) 
{ 
    Tree *tree1 = new Tree; 
    tree1->right_son = nullptr 
    tree1->left_son = nullptr 

Или вы можете сделать то же самое в дереве struct, добавив в конструктор конструктор.