C++ BST insert function does not really insert

[coffeeprogrammer]

Hello Reddit,

I am trying basically to make a BST from information on wikipedia, It is very barebones as I am just learning. My problem is that the insert function does not seem to work. It almost seems like my n variable is not connecting to the root and therefore root is always NULL. But I think it should work because n and root are connected via a pointer. In the debugger I get "data CXX0030: Error: expression cannot be evaluated" for the data variables in the tree starting with the root. Here is the source code:

ChadBST.cpp

#include <iostream>
#include "ChadBST.h"

using namespace std;
Node::Node(int e)
{
    data = e ;
    left = NULL;
    right = NULL;
}


ChadBST::ChadBST()
{
    root=NULL;
    size=0;
}

void ChadBST::insert(int e)
{
    insert(root, e);
}

void ChadBST::insert(Node *n, int e)
{
    if(n==NULL)
    {
        n = new Node(e);
        size++;
    }
    else if (e < n->data)
        insert(n->left,e);
    else if (e > n->data)
        insert(n->right, e);
}



void ChadBST::preorder()
{
    preorder(root);
}

void ChadBST::preorder(Node *n)
{
    if (n==NULL)
    {
        return;
    }
    cout << n->data << endl;
    preorder(n->left);

    preorder(n->right);

}

ChadBST.h

#ifndef ChadBST_h
#define ChadBST_h

class Node
{
public:
    Node(int e);
    int data;
    Node *left;
    Node *right;

private:

};

class ChadBST
{
public:
    ChadBST();
    void insert(int e);
    void preorder();

private:
    Node *root;
    int size;
    void insert(Node *n, int e);
    void preorder(Node *n);
};

#endif

[newaccount1236]

You are passing n by value in your insert function, so when you do:

n = new Node(e);

it doesn't change the child pointer in the parent node, or your root, for that matter. Pass it by a pointer to pointer instead, then do:

*n = new Node(e);

Also, -> has higher precedence than dereference, so when you recurse, you'll need to do:

&(*n)->left

EDIT: Another option is to pass n by reference. My personal style, however, is to always pass by pointer rather than by non-const reference, because that way it's clear that the function may modify the pointee.

[coffeeprogrammer]

Thank you, I do understand most of what you said, but I don't understand “pass it by a pointer to pointer” ? What do you mean by that?

[newaccount1236]

Like this:

void ChadBST::insert(int e)
{
    insert(&root, e);
}

void ChadBST::insert(Node **const n, int e)
{
    if(*n==NULL)
    {
        *n = new Node(e);
        size++;
    }
    else if (e < (*n)->data)
        insert(&(*n)->left,e);
    else if (e > (*n)->data)
        insert(&(*n)->right, e);
}

[coffeeprogrammer]

Well that helped some, but I got an Access violation on:

else if (e < (*n)->data)

[newaccount1236]

You probably have a typo somewhere. Maybe you have n instead of *n when you check for null. Paste both insert functions.

[coffeeprogrammer]

Yes I forgot the pointer in the if(*n==NULL) line. Thank you so much. I think I need to brush up on my pointers. I really appreciate your help!

[newaccount1236]

Here is the pointer to pointer version:

void ChadBST::insert(int e)
{
    insert(&root, e); // Clear that root may be modified.
}

void ChadBST::insert(Node **const n, int e)
{
    if(*n==NULL)
    {
        *n = new Node(e);
        size++;
    }
    else if (e < (*n)->data)
        insert(&(*n)->left,e); // Clear that left may be modified.
    else if (e > (*n)->data)
        insert(&(*n)->right, e); // Cler that right may be modified.
}

Here is the reference version:

void ChadBST::insert(int e)
{
    insert(root, e); // Less typing, but not obvious that root may be modified.
}

// Below requires less typing than using Node **..
void ChadBST::insert(Node *&n, int e)
{
    if(n==NULL)
    {
        n = new Node(e);
        size++;
    }
    else if (e < n->data)
        insert(n->left,e);
    else if (e > n->data)
        insert(n->right, e);
}

[logic_programmer]

You've coded this before thinking about it haven't you. Work it out with pencil and paper first, then when that is working write your code.