Passing by pointers

Question

I'm working on a C++ program for school with VS13. I need to insert data into a BST. I was given a function defined as Add(int dataValue); (under public) which only takes the data value. I defined a second Add() function that also takes a Node* as a parameter so as to make Add() recursive. (see .h portion of code below)

#include <iostream>
#include <queue>

class HW2BST
{
private:
    struct Node
    {
        int Data;
        Node* Left;
        Node* Right;

        Node(int dataValue);
    };

    Node* m_root;

    bool Add(Node* root, int dataValue);

public:
    bool Add(int dataValue);

My problem is that when tree.Add(int) is called from main, I try and then pass m_root into the second Add(Node*, int) function to insert the data. Stepping through the function and watching m_root and root as it runs I see that inside of Add(Node*, int) root is set to NULL as I expected. As it steps through root->Data is correctly assigned the dataValue, and root->Left and root->Right are correctly assigned to NULL. But those assignments don't pass back to m_root. Once the function exits, root is destroyed, m_root is not updated and I'm left with no tree. (see .cpp below)

#include "HW2BST.h"

using namespace std;

HW2BST::Node::Node(int dataValue)
{
    Data = dataValue;
    Left = Right = NULL;
}

HW2BST::HW2BST(void)
{
    m_root = NULL;
}

bool HW2BST::Add(int dataValue)
{
    return Add(m_root, dataValue);          // Add (overload) recursively searches then inserts dataValue, then returns result
}

bool HW2BST::Add(Node* root, int dataValue)
{
    if (!root)                              // verify if node exists
    {
        root = new Node(dataValue);         // if node does not exist, implement new node and set dataValue
        if (!root)                          // if node not allocated correctly, return false
            return false;
        else                                // else return true (both new node implemented and value added to tree)
            return true;
    }
    else if (dataValue < root->Data)            // if not empty, check data value with current data
        return Add(root->Left, dataValue);      // if less than, travel down left child
    else if (dataValue > root->Data)
        return Add(root->Right, dataValue);     // if greater than, travel down right child
    else
        return false;                           // if equal to, ignore (double entry)
}

I have talked to my professor and he said something about using Node** instead, but when I tried that I couldn't get the types to reconcile (i.e. root->Data kept throwing error C2227).

I know the solution is simple, I just can't seem to grasp what I'm missing.

Answer 1

Here is a problematic line:

root = new Node(dataValue);

It's problematic because C++ by default passes arguments by value, and that goes for pointers as well. This means that inside the function root is a copy of the original pointer, and changing a copy will of course not change the original.

You need to pass the pointer by reference:

bool Add(Node*& root, int dataValue);

---

You can of course emulate pass by reference using pointers, like it's done in C, but then you have to remember to dereference the pointer as well as use the address-of operator & when passing the pointer. But since C++ have proper references this is not needed.