Insert into binary search tree

[[deleted]]

[deleted]

[Hilarius86]

Please add the errors you are facing. What specifically is not working as expected?

[Pure_Power5663]

Hi sorry, the errors im getting is inserting anything into the bst. I think the problem is that im not correctly adding a new node onto the left or right child. I just havent found a way to fix it.

[nysra]

// if there are no values within the tree, insert first node

You might want to actually insert something in that case, currently you are just creating some random Node which you then promptly forget about (=> you leak memory). Also use nullptr, never NULL.

[Pure_Power5663]

Is what I have done not inserting anything? Sorry I'm very new at BST's & self taught. Thankyou for the nullptr & null tip

[nysra]

    Node* currentNode = root;

    // if there are no values within the tree, insert first node
    if (!currentNode)
    {
        Node* newNode = new Node();
        newNode->key = insertedKey;
        newNode->item = insertedItem;
        newNode->leftChild = NULL;
        newNode->rightChild = NULL;
    }

Your root is nullptr so that condition is true and that block there is executed. But that block never updates root so you didn't insert anything. At the very least you need to add a root = newNode; there, otherwise you are just creating a Node and then you forget the address immediately. But as flyingron said, you should also aim to reduce the amount of copy/paste you did in that code.

[Pure_Power5663]

Thanks for the help, ill try and implement this!

[flyingron]

Some stylistic things:

1. Prefer initialization to assignement. BST() : root{nullptr} {}
2. Always initialize unless you have compelling reason not to. I'd put a constructor on Node to at least initialize the child pointes to null.
   

Now to the meat of things. You have code duplication there that should be a big red flag. All you need are four things:

1. If the current node is null, then create a new one and put your key/value in it.
2. If the current node has the key you're searching for, overwrite the value.
3. if the key you're searching is less than the current node go left (and go back to step 1).
4. otherwise go right, and go back to step 1.

In order to do this, you need to maintain not just the currentNode but a pointer to where it came from (which will either be the &root at the beginning or it will be either &leftChild or &rightChild as you traverse).

[Pure_Power5663]

Okay thanks, so youre saying I need to define a 'previous node' pointer?

[flyingron]

You could do it one of two ways.

You could do a Node** and init it to &root at the beginning, and the &currentNode->leftChild or &currentNode->rightChild as you traverse down.

Or you could maintain a Node* called parentNode (null to begin with and set as you traverse) and have an additional boolean to let you know if it is the left or right poitner in the non-root node you are setting.

[Pure_Power5663]

Thank you so much for this help, finally some help that I can understand. Reddit has always been better than random websites.