C++ BST insertion

Question

I'm implementing a BST using C++, but after I implemented the insert function, I found that I can only insert one node into the tree. I've tried many ways to solve the problem, but they didn't work out...

Here's my implementation of insert function:

void BSTree::insertHelper(Customer* customer, Node* currentNode, Node* parent)
{
    if (currentNode == NULL)
    {
        Node* newNode = new Node(customer);

        currentNode = newNode;
        newNode->setParent(parent);

        return;
    }

    if (*customer < *currentNode->getCustomer())
        insertHelper(customer, currentNode->getLeft(), currentNode);
    else insertHelper(customer, currentNode->getRight(), currentNode);
}

bool BSTree::insert(string lastName, char initial, int account)
{
    Customer* customer = new Customer(lastName, initial, account);

    if (isEmpty())
    {
        Node* newNode = new Node(customer);

        root = newNode;

        return true;
    }

    Node* currentNode = root;
    insertHelper(customer, currentNode, NULL);

    return true;
}

Thank you for all your helps.

Answer 1

You leak memory. Look here at insertHelper:

if (currentNode == NULL)
{
    Node* newNode = new Node(customer);

    currentNode = newNode;
    newNode->setParent(parent);

    return;
}

currentNode is a local variable. It exists only inside insertHelper. So if you assign to it, that won't be reflected outside the function when you return. You pass the parent along, so assign to its left or right member:

newNode->setLeft(parent);
// or
newNode->setRight(parent);