Error while inserting element into binary search tree

Question

The program creates a binary search tree from a sorted array of numbers and adds elements to it.

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;
        }
    }
}

The problem is in line if (curr_pos->left_son != nullptr) , when node has no left "son", condition satisfies for some reason, but it shouldn't. I mean program finds left "son" even if there's no one, and the pointer moves there. Sorry, my english is bad, but I hope somebody can understand what I said.

Do you always initialize left_son and right_son to nullptr?? — ivanw
– ivanw, Commented Jun 20, 2015 at 15:47
@ivanw probably not, where exactly should I do this? thanks for answer btw! — Turtle Sergio
– Turtle Sergio, Commented Jun 20, 2015 at 15:53

ivanw · Accepted Answer · 2015-06-20 15:58:45Z

1

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

Or you could do same in the struct Tree by adding a contructor to the struct.

answered Jun 20, 2015 at 15:58

ivanw

5118 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Error while inserting element into binary search tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related