BST implementation help

[mandrewb]

I am working an a BST implementation for class and I need help pinpointing the cause of my segfaults in my insert function code.

My binary node's look like:

    private:
        struct BinaryNode
        {
            Type element;
            BinarySearchTree<Type> *left;  //name of BST class
            BinarySearchTree<Type> *right;
            BinaryNode(const Type &item,
                       BinarySearchTree<Type> *leftTree,
                       BinarySearchTree<Type> *rightTree)
                    : element(item), left(leftTree), right(rightTree) {}
        };
        BinaryNode *root;

        Type getElement() const
        { return root->element; }
        BinarySearchTree<Type> *getLeft() const
        { return root->left; }
        BinarySearchTree<Type> *getRight() const
        { return root->right; }

Here is my insert function:

    template <typename Type>     //made private
    void BinarySearchTree<Type>
            ::insert(const Type &item,
                     BinarySearchTree<Type> *tree)
    {
        if (tree == NULL)
        {
            tree = new BinarySearchTree<Type>;
            tree->root = new BinaryNode(item, NULL, NULL);
        }
        else if (item < tree->getElement())
            insert(item, tree->getLeft());
        else if (item > tree->getElement())
            insert(item, tree->getRight());
    }

    template <typename Type>    //made public
    void BinarySearchTree<Type>::insertElement(const Type &item)
    {
        insert(item, this);
    }

To me this function is making perfect sensevbut obviously something is not right. Thanks for the help.

[LB]

You pass the pointer to tree by value, but then you try to assign to it - this only affects it within the scope of the function.

Try passing by reference: BinarySearchTree<Type> *&tree

[mandrewb]

Thanks. I'm now trying to tackle errors I get when I try to use the function.
Error:

BST.h:147:9: error: no matching function for call to ‘BinarySearchTree<int>::insert(const int&, BinarySearchTree<int>*)’
BST.h:133:6: note: candidate is: void BinarySearchTree<Type>::insert(const Type&, BinarySearchTree<Type>*&) [with Type = int]

But, item is of type Type and tree->getRight() is of type BinarySearchTree<Type>. I don't understand.

[LB]

tree->getRight() needs to return a reference as well.
(And probably tree->getLeft() too)

[mandrewb]

There is still an error when insertElement function tries to call the private insert function. Am I properly using the this pointer?

[LB]

I think you have a design flaw. If insert can only be called with a valid pointer, why are you checking for the pointer to be null? If you intend it to be called externally, why is it being called from the same instance that uses it?

In most linked list implementations I've seen, you don't assign to the node you have been passed. You assign to a pointer within the node you have been passed.

I led you though a wild goose chase in the hopes you would notice your mistake - now I am telling you: you need to redesign your code some.