Binary Tree: Copy Constructor

Question

I have to create a copy constructor for a binary tree with the signature bstt(const bstt& other). I attempted to do so, but I get the following error (in the last code block).

I thought I needed to change my helper function signature to include a const, but I tried a few combinations and none of them worked. How can I fix this?

Helper function:

void _postordercopy(NODE*& thisT, const NODE*& otherT)
{
 if(otherT==nullptr){
  thisT=nullptr;
 }
 else
 {
  NODE* tmp=new NODE;
  tmp->Key=otherT->Key;
  tmp->Value=otherT->Value;
  tmp->Left=otherT->Left;
  tmp->Right=otherT->Right; 
  tmp->isThreaded=otherT->isThreaded;

  _postordercopy(thisT->Left,otherT->Left);
  _postordercopy(thisT->Right,otherT->Right);
 }
}

Copy Constructor:

  bstt(const bstt& other)
  {
   Size=other.Size;
   _postordercopy(Root,other.Root);
  }

Error Message:

bstt.h:110:35: error: no matching function for call to ‘bstt<int, int>::_postordercopy(bstt<int, int>::NODE*&, bstt<int, int>::NODE* const&)’

In your function `bsst(const bsst&)`, the variable `other` is `const`. Meaning you have provided a contract to anyone calling this function that `other` will not be modified. `bsst(const bsst&)` cannot send `other` to `_postordercopy`, because it doesn't know if `_postordercopy` will make any changes to `other`. Change the function signature of `_postordercopy` so that the second parameter is `const Node*& otherT`, so that the copy constructor can honor its own `const` contract. — JohnFilleau, Feb 29 '20 at 04:01
@John I get the error: ```no known conversion for argument 2 from ‘bstt::NODE*’ to ‘const bstt::NODE*&’``` — thegoodhunter-9115, Feb 29 '20 at 04:04
I guess give it the signature it wants then. I don't know the `const` rules as well as i thought. — JohnFilleau, Feb 29 '20 at 04:12

score 0 · Accepted Answer · answered Feb 29 '20 at 05:00

You are creating a tmp node in your _postordercopy function, assigning to it, but aren't doing anything with it. Further, you are copying over the exact pointers for Left and Right. That doesn't look right either.

I think this is what you really want for a recursive "copy the tree" function:

    NODE* copyTree(const NODE* other)
    {
         NODE* newTree = nullptr;

         if (other!=nullptr)
         {
             newTree = new NODE;
             newTree->Key = other->Key;
             newTree->Value = other->Value;
             newTree->isThreaded = other->isThreaded;
             newTree->Left = copyTree(other->Left);
             newTree->Right = copyTree(other->Right);
         }

         return newTree;
    }

And then in your copy constructor, just invoke it as follows:

    bstt(const bstt& other)
    {
        this->Size = other.Size;
        this->Root = copyTree(other.Root);
    }

score 0 · Answer 2 · answered Feb 29 '20 at 06:59

I will assume that bstt::Root is declared as NODE*, as this seems most likely.

The second parameter to _postordercopy is of type const NODE*&, a reference to a pointer to a constant NODE. What is the type of the argument you try to pass in? Since other is declared const, each of its members is const. So other.Root is a constant pointer to NODE, also known as NODE* const – the const is tacked on the far right of the declared type. This is incompatible with the parameter type. (See What is the difference between const int*, const int * const, and int const*? for a more thorough discussion of this distinction.)

The problem is that a non-constant reference cannot be initialized from a constant. Since other has to be const, you'd need to change the type of the function parameter to match what you give it. One solution is to move const so that it qualifies the pointer rather than the pointer-to object: NODE* const &. Another solution is to remove the ampersand, as that is a bit wasteful in this case: const NODE*. (The reference adds an extra layer of indirection that provides no benefit.) Think about what your function is supposed to do, and const-qualify whatever is supposed to not change. In this case, the node pointed to by the second parameter should not change.

While that resolves your immediate compiler error, there are other errors to address in your code. In addition, I would consider adding two accessor functions to get the root node. These functions could enforce const in a way that you do not get when accessing Root directly.

NODE *& get_root() { return Root; }
const NODE * const & get_root() const { return Root; }

The main difference is that the type of other.Root is NODE * const, which drops the const-qualifier for the node, whereas other.get_root() would yield a const NODE * const, which propagates the qualifier. At the same time, this->get_root() would yield a simple NODE* since this is not const-qualified. You get to use the same syntax, and the const-ness is propagated appropriately.

Binary Tree: Copy Constructor

2 Answers2