"Node" not declared in scope error even though "Node" is declared inside Tree class

Question

I am not able to figure out why I get the compilation error

  5 class Tree {
  6  public:
  7     Tree() : root(nullptr) { std::cout << "tree created" << std::endl; }
  8     ~Tree() { std::cout << "tree destroyed" << std::endl; }
  9     bool add(int val);
 10     void inOrderTraversal() { inOrderTraversal(root); }
 11
 12  private:
 13     struct Node {
 14         int data;
 15         std::shared_ptr<Node> left;
 16         std::shared_ptr<Node> right;
 17         Node(int val) : data(val), left(nullptr), right(nullptr) { std::cout << "tree node created: " << data << std::endl; }
 18         ~Node() { std::cout << "tree node destroyed: " << data << std::endl; }
 19     };
 20
 21     void inOrderTraversal(std::shared_ptr<Node> node);
 22     std::shared_ptr<Node> insert(int val, std::shared_ptr<Node> subTree);
 23     std::shared_ptr<Node> root;
 24 };
 25
 26 std::shared_ptr<Node> Tree::insert(int val, std::shared_ptr<Node> subTree) {
 27     if (subTree == nullptr) {
 28         std::shared_ptr<Node> node = std::make_shared<Node>(val);
 29         return node;
 30     }
 31
 32     if (val <= subTree->data) {
 33         subTree->left = insert(val, subTree->left);
 34     } else {
 35         subTree->right = insert(val, subTree->right);
 36     }
 37     return subTree;
 38 }

But I get the following compilation errors:

g++ -std=c++11 boot_camp.cpp
boot_camp.cpp:26:17: error: ‘Node’ was not declared in this scope
 std::shared_ptr<Node> Tree::insert(int val, std::shared_ptr<Node> subTree) {
                 ^
boot_camp.cpp:26:21: error: template argument 1 is invalid
 std::shared_ptr<Node> Tree::insert(int val, std::shared_ptr<Node> subTree) {
                     ^
boot_camp.cpp:26:23: error: prototype for ‘int Tree::insert(int, std::shared_ptr<Tree::Node>)’ does not match any in class ‘Tree’
 std::shared_ptr<Node> Tree::insert(int val, std::shared_ptr<Node> subTree) {

I dont understand why it complains that "Node" is not declared in scope. I did declare "Node" inside of the Tree class.

And I don't see the error in a different function like:

 55 void Tree::inOrderTraversal(std::shared_ptr<Node> node) {
 56     if (node) {
 57         inOrderTraversal(node->left);
 58         std::cout << node->data << " ";
 59         inOrderTraversal(node->right);
 60     }
 61 }

Answer 1

Node is an inner class of Tree. Change your references outside of the class definition to Tree::Node so g++ looks in the right namespace for your definition.

Like this:

std::shared_ptr<Tree::Node> Tree::insert(int val, std::shared_ptr<Node> subTree) {
   ...
}

You'll also want to fix your return true in your insert function since you should return a std::shared_ptr<Tree::Node> instead.

Also, in a comment Suhas made a good point I didn't notice that you only need the Tree:: scope for return values (Tree::inOrderTraversal for example). This appears to be because inside the function inOrderTraversal, the compiler will look in the existing class for the definition of Node per the C++ 11 Standard Section 3.4.1 rules on Unqualified name lookup. It won't apply this rule though for the return value, which is outside the function.