Identifier Node* is undefined(linker problem)

Question

I am really sorry if this is a duplicate post, but I am really stuck on this particular problem. For some inexplicable reason the compiler does not understand what return type Node* is on the .cpp file, here is the code:

template<typename T>
Node* BinarySearchTree<T>::DiveDownToReplace(Node* node) {
    if (node->leftChild->rightChild == nullptr) {
        return node->leftChild;
    }
    //otherwise
    Node* traversingNode = node->leftChild;
    Node* returnedNode;
    while (true) {
        if (traversingNode->rightChild->rightChild == nullptr) {
            returnedNode = traversingNode->rightChild;
            traversingNode->rightChild = returnedNode->leftChild;
            returnedNode->leftChild = nullptr;
            break;
        }
        traversingNode = traversingNode->rightChild;
    }
    return returnedNode;

}

Here is also the code in the .h(header file):

#pragma once
template<typename T>
class BinarySearchTree {
private:

    struct Node
    {
        T data;
        Node* leftChild;
        Node* rightChild;
    };

    int m_Length = 0;
    Node* root = new Node();

public:
    enum class TraverseMethod
    {
        preorder,
        inorder,
        postorder,
        levelorder
    };

    ~BinarySearchTree();
    void AddElement(T value);
    T RemoveRoot();
    bool RemoveElement(T value);
    void PrintAllElements(TraverseMethod traverseMethod);
    bool IsEmpty();
    bool GetSize();
    bool Contains(T value);

private:

    void PreOrder(Node* node);
    void InOrder(Node* node);
    void PostOrder(Node* node);
    void LevelOrder(bool deleteNode = false);
    void DiveDownToAdd(T value, Node* node);
    Node* DiveDownToReplace(Node* node);
};

I am getting the error "identifier Node is undefined". I tried adding BinarySearchTree::Node* instead of Node*, but I received some weird errors(c2061, syntax error: identifier 'Node'). Once more I am sorry if this post is duplicate, but coming from languages like c# and Java I am really fed up with these header issues. Thank you in advance!

Answer 1

There are two rather complicated technical details of C++ that get combined together here. First of all, is scoping and namespaces.

    //otherwise
    Node* traversingNode = node->leftChild;

This is code that's inside a member function of the BinarySearchTree template. When a symbol, such as Node gets used the compiler needs to know what in blazes is that. BinarySearchTree defines an inner class named Node, so there you go. Problem solved.

template<typename T>
Node* ...

But what the heck is this? What is this weird Node all about? This part of the C++ code is not inside a member function. You better have a global class, or something, named Node, or you'll be in big trouble.

Just because there happens to be some class or template that's defined, and it has an inner class named Node, well this means absolutely nothing, whatsoever. When some symbol name is used, in global scope, the compiler is not going to search every class for something that happens to have the same name. C++ does not work this way.

And that's why you must spell everything out:

template<typename T>
typename BinarySearchTree<T>::Node *

The "template<typename T>" stuff makes a grandiose entrance of a template parameter that's represented by symbol T, and BinarySearchTree<T>::Node spells everything out.

And the second part of this story, the only remaining question here, is what in blazes is that typename all about.

Well, that's a long story, that you can read by yourself.