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

Question

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

If `ptr` is `nullptr` you will allocate a new `node` and then leak memory because the new `node` is inaccessible after `insert` returns. — nwp, Apr 15 '17 at 18:24
So how should I go about fixing that? I'm new to coding and this website. I feel like people on this site, like to down-vote new people instead of helping them. — aashman, Apr 15 '17 at 18:30
@aashman Not true. It's just a lot of people new to StackOverflow (and it's partner sites) assume it's a free debugging service, rather than a community driven knowledge resource. — Daniel, Apr 15 '17 at 18:34
People are downvoting because you give them a beginner question which you could have answered yourself with a [book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). It would have told you that parameters are copied and you want to replace `node* ptr` with `node* &ptr`. — nwp, Apr 15 '17 at 18:36

score 0 · Accepted Answer · answered Apr 15 '17 at 18:27

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

Thank you! that worked. I originally tried passing a pointer to node in that function, but I guess I forgot to do something. — aashman, Apr 15 '17 at 18:37

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

1 Answers1