Array implementation of Binary Search Tree

Question

I am creating a binary search tree using a 1D array. My problem is with the insertion function.

Inserting 5, 8, 3, 1, 4, and 9 results in the correct index when I output the tree. However, when I try to add numbers after 9 into the tree, the index is incorrect. For example, with the previous numbers mentioned, 9 has an index of 7. If I insert 17, which should be 9's right child, instead of its index at 15, it's index is 11.

I know that the issue is with how I increment i but I'm not sure how to fix it. Any help is appreciated. Thanks!

    void insert(int x)             
    {   
    int i = 1;  //Counter

    if (ptr->arr[1] == -1)   //If bst is empty.
    {
        ptr->arr[1] = x;
    }
    else                    
    {
        int *temp = &ptr->arr[1];  //Temp starts at root
        int *parent = NULL;
        while (*temp != -1 && *temp != x)
        {
            if (x < *temp)
            {
                parent = temp;
                temp = &ptr->arr[i*2];
                i++;
            }

            else
            {
                parent = temp;
                temp = &ptr->arr[i*2+1];
                i+=2;
            }

        }

        *temp = x;

    }

Nico Schertler · Accepted Answer · 2017-12-06 18:43:50Z

1

You are maintaining the current node in two different variables: a pointer to the node is kept in temp and the index of the node is kept in i. This by itself - although probably not optimal - is not a problem. However, you don't keep the two variables consistent (you update the pointer differently than the index). A simple fix would be to make this consistent:

temp = &ptr->arr[i*2]; //the pointer update is correct
i = i * 2; //same update as above
//...
temp = &ptr->arr[i*2+1];
i = i * 2 + 1; //same update as above

In my opinion, it is also a good idea to drop the pointer temp completely and always access the array by its index. This would not require any synchronization between two variables.

answered Dec 6, 2017 at 18:43

Nico Schertler

32.7k4 gold badges45 silver badges76 bronze badges

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

2 Comments

j.pebbles Over a year ago

Thank you. I tried the other changes you made above and I got a runtime error. I think dropping the temp is the way to go.

Nico Schertler Over a year ago

Then your array might not be large enough.

Collectives™ on Stack Overflow

Array implementation of Binary Search Tree

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related