CODEWITHSUNDEEP
c++arraysbinary-search-tree
j.pebbles
j.pebbles

Reputation: 3

Array implementation of Binary Search Tree

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;

    }

Upvotes: 0

Views: 459

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32597

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.

Upvotes: 1

Related Questions