binding reference of type const node*& to node*const

Question

I am trying to implement a generic tree and in the function getSizeRecursive line 1why cannot i use const node* &root. Similarly, i am getting the same mistake in line 2.The compiler is giving an error which i am not able to comprehend.

graph.cpp: In function 'int getSizeRecursive(const node*&)':
graph.cpp:56:40: error: binding reference of type 'const node*&' to 'node* const' discards qualifiers
   56 |         for(const node* &child : root->children) // line 2
      |                                        ^~~~~~~~
graph.cpp: In function 'int main()':
graph.cpp:69:36: error: binding reference of type 'const node*&' to 'node*' discards qualifiers
   69 |         cout << getSizeRecursive(t.root) << endl;
      |                                  ~~^~~~
graph.cpp:51:35: note:   initializing argument 1 of 'int getSizeRecursive(const node*&)'
   51 | int getSizeRecursive(const node* &root){ // line 1
      |                      ~~~~~~~~~~~~~^~~~
[Finished in 2.9s]

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class node{
public:
    int data;
    vector<node*> children;

    node(int val){
        data = val; // this->data = data
    }
    ~node(){
        for(int i = 0 ;i<children.size();i++){
            if(!children[i])
                delete children[i];
        }
    }
};
class GenericTree{
public:
    node* root; // line 3
    int size;
    
    GenericTree(vector<int> nums){
        stack<node*> st;
        size = 0;
        for(int i = 0;i<nums.size();i++){
            node *n = new node(nums[i]);
            if(i == 0){
                root = n;
                st.push(n);
                ++size;
            }else{
                if(n->data == -1){
                    st.pop();
                }else{
                    // cout << "In me" << endl;
                    st.top()->children.push_back(n);
                    st.push(n);
                    ++size;
                }
            }
        }
    }
    // tells us the number of nodes
    int getSize(){
        return size;
    }
};
int getSizeRecursive(const node* &root){ // line 1
    if(root->children.size()==0)
        return 1;

    int size = 0;
    for(const node* &child : root->children) // line 2
        size  += getSizeRecursive(child);
    return size+1;
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
    vector<int> v{10,20,-1,30,50,-1,60,-1,-1,40,-1,-1};
    GenericTree t(v); // node that tree has been created 
    cout << t.size << endl;
    cout << getSizeRecursive(t.root) << endl;
    return 0;
}

What i can understand from this is that compiler is not able to bind the reference to pointer to const node to const pointer to node but my question is that why it is taking t.root as const pointer to node whereas in actual it is just a pointer to node(see line no 3).

I am novice in c++. Any help would be appreciated.

EDIT: The reason i have used const* & root is because i did not want to pass a copy of root to getSizeRecursive but during that since i have passed by reference i have used const so that this reference just only reads the root pointer and not modify it.

Answer 1

Let's see the reason for getting each of the error on case by case basis. Moreover, i'll try to explain things in steps.

Case 1

Here we consider the 1st error due to the statement:

for(const node* &child : root->children)

Now to understand why we get error due to the above statement, let's understand the meaning of each term in step by step manner:

Step 1:

root is a non-const lvalue reference to a non-const pointer to const node. This means that we're allowed to change the pointer to which root refers(since we've a nonconst lvalue ref) but we're not allowed to change the actual node object to which that pointer is pointing.

Step 2

root->children is const vector<node*> since we're not allowed to change the node object to which the pointer is pointing as discussed in step 1 above. Basically, it is as if the pointed to object is itself const which in turn means its data members are treated as const as well. And as children is a data member so it is treated as const and thus root->children is const vector<node*>.

Note the conclusion of this step is that we have a const vector with elements of type node*.

Step 3

Now, const node* &child means that child is a non-const lvalue reference to a nonconst pointer to a const node. Again, this means that we're allowed to change the pointer residing inside the vector. But this is a problem because we learnt from step 2 above that we've a const vector<node*> meaning that we should not be allowed to change the pointer residing inside the vector. And hence you get the mentioned error.

Solution to case 1

To solve this you need to make sure that there is no way to change the pointer residing inside the const vector by adding a low-level const as shown below:

//-------vvvvv--------------------------->const added here
for(node*const &child : root->children)

The above works because now child is a lvalue reference to a const pointer to a nonconst node object.

Case 2

Here we consider the 2nd error due to the expression:

getSizeRecursive(t.root)

Here the passed argument t.root is a node* while the parameter is a const node* &. Now, the passed argument is implicitly convertible to const node* but result of that conversion will be an rvalue. But since the parameter root is an nonconst lvalue reference to a non-const pointer to const node it cannot be bound to an rvalue.

This is basically the same error that you will get using:

node *ptr;
const node*& ref = ptr; //will produce the same error saying: error: cannot bind non-const lvalue reference of type ‘const int*&’ to an rvalue of type ‘const int*’

Solution to Case 2

Basically, a given type T can be bound to T& or T const& while a given type const T can be bound to T const&. And in your example, the passed argument is node* meaning it can be bound to both node*& as well as node*const&.

To solve this you can make the lvalue reference to a const lvalue reference as shown below:

node *ptr;
//---vvvvv--------------->const added here
node*const& ref = ptr;

In your example, this means:

//------------------------vvvvv--------->const added here
int getSizeRecursive(node*const &root){ // line 1

Working demo