BST - inserting + C++

Question

I'm trying to work on a binary search tree data structure, but I cannot seem to accomplish inserting anything into the tree. Every time my program calls the insert function, it believes there is nothing in tree. Here are the 2 classes:

template<typename T>
class TreeNode{
public:
    T m_data;
    TreeNode* m_right;
    TreeNode* m_left;
    TreeNode<T>(const T& data, TreeNode<T>* right, TreeNode<T>* left) : m_data(data), m_right(right), m_left(left){};
};

template<typename T>
class MyBSTree : public AbstractBSTree<T>{
protected:
    TreeNode<T>* m_root;
    int m_size;

And here is the function:

    void rec_insert(TreeNode<T>* root, const T& x){
        if(root == NULL){
            cout << "Inserting here" << endl;
            TreeNode<T>* tmp = new TreeNode<T>(x, NULL, NULL);
            root = tmp;
        }
        else if(x < root -> m_data){
            cout << "Inserting left" << endl;
            rec_insert(root -> m_left, x);  
        }
        else if(x > root -> m_data){
            cout << "Inserting right" << endl;
            rec_insert(root -> m_right, x);
        }
        if(root == NULL)
            cout << "WHAT IS HAPPENING?" << endl;
        cout << "resizing" << endl;
        m_size++;
    };

The output for inserting a couple of items is this:

Inserting here
resizing
Inserting here
resizing

I really have no clue what is going on here, any help would be greatly appreciated.

you changed value of root inside your function but it will not reflect in your calling function. that is your problem. — 999k, Nov 14 '13 at 03:45
Check this http://stackoverflow.com/questions/1398307/how-can-i-allocate-memory-and-return-it-via-a-pointer-parameter-to-the-calling — 999k, Nov 14 '13 at 03:48

score 0 · Answer 1 · answered Nov 14 '13 at 03:46

You need to do a bit of research on pass by reference and pass by value.

You pass a pointer into your insert method - you can only change the value of root locally - any change you make won't persist beyond the function call. You need to pass by reference to allow root to be changed and see that change outside the rec_insert() method.

Another approach may be to refactor your code to return the root value from rec_insert().

BST - inserting + C++

1 Answers1