Referencing an ADT within a header file

Question

I'm trying to implement a binary search tree in C++ (for a college class) and I am having some difficulty accessing a struct I defined in the .h file.

Here is my .h file:

class BST
{
    protected:
        struct node 
        {
            int data;
            node* left;
            node* right;
        };
        node* insert(int x, node* t);
        node* root;
       
    public:
        BST();
        void insert(int x);
};

and the implementation file:

    node* BST::insert(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->left = t->right = NULL;
        }
        else if(x < t->data)
            t->left = insert(x, t->left);
        else if(x > t->data)
            t->right = insert(x, t->right);
        return t;
    }

The node struct is defined in the .h file and is used as a return type for the insert function. it's also being used within the insert function itself. My issue is that the current method signature results in 2 errors:

unknown type name 'node'

along with:

cannot initialize return object of type int* with an lvalue of type BST::node *

However, if I change the method signature to:

    BST::node* BST::insert(int x, node* t)

The errors are resolved. I understand why this would resolve the errors regarding the return type, but within the function itself I have a variable that uses that data type:

t = new node

how does t know what data type node is without the extra BST:: in front of it?

user_2877241 · Answer

If you are defining the function outside the class definition then the unqualified name node used as a return type is searched in the enclosing namespaces where the class is defined.

In the function declarator and within the function body the unqualified name node is searched starting from the class definition (provided that the name used within the function is not redeclared in one of enclosing blocks. Otherwise the name is searched starting from this nested block).

Referencing an ADT within a header file

1 Answers