aashman aashman - 3 years ago 51
C++ Question

Why won't this insert function update my binary search tree?

I'm basically trying to insert a number into my tree. Initially I pass the command insert(root, 10), and then my function recursively traverses through the tree to insert the value. The traversal works fine, but my tree won't get updated. I already built a tree in this class through my constructor. The inorder traversal of my tree before the insert function is {0, 1, 2, 3, 4, 5, 6, 7 ,8, 9}, and its the same after the insertion as well


My insert function:


private:

node* root

void insert(node* ptr, int num) {
if (ptr == NULL) {
ptr = new node;
ptr->data = num;
ptr->left = NULL;
ptr->right = NULL;
return;
}

else if (ptr->data >= num) {
insert(ptr->left, num);
}

else if (ptr->data < num) {
insert(ptr->right, num);
}
}



private member of my class that creates initial tree


node* createTree(int array[], int start, int end) {

if(start > end) {
return NULL;
}

int mid;
node* newNode = new node;

if (((start + end) % 2) != 0) {
mid = ((start + end) / 2) + 1;
}

else {
mid = (start + end) / 2;
}

newNode->data = array[mid];
newNode->left = createTree(array, start, mid - 1);
newNode->right = createTree(array, mid + 1, end);

cout << newNode->data << " " << newNode << endl;

return newNode;
}



The constructor


BST(int array[], int length) {
root = createTree(array, 0, length - 1);
}

Answer Source

You need to make sure that the parent is updated when you allocate a new node. One way to do so is to let insert return the node pointer:

node* insert(node* ptr, int num) {
        if (ptr == NULL) {
                ptr = new node;
                ptr->data = num;
                ptr->left = NULL;
                ptr->right = NULL;
        } else if (ptr->data >= num) {
                ptr->left = insert(ptr->left, num);
        } else {  // ptr->data < num 
                ptr->right = insert(ptr->right, num);
        }
        return ptr;
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download