Binary Tree Assignment Operator Overload Problem C++

Question

I am trying to overload the assignment operator for my Binary Search Tree.

Example: tree1 = tree2

I want to delete all the nodes in tree1 and make deep copy of all nodes in tree.

I already have function:

Node* deepCopyTree(const Node *source)

which works perfectly well. I created also this function:

void deleteTree(Node* root)
{
    if (root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }
}

which as I see my debugging it works. The operator overload function :

    BST& BST::operator=(const BST &rhs) 
{
    DestroyRecursive(root);
    deepCopyTree(rhs.root);
    return *this;

}

And that throws me an error when copying.. I am working from 10 hours on that and this is the smallest thing I have left with and I want to finish it. Please help :) .

That is my deep copy constructor:

BST::BST(const bST&rhs)
    :root(deepCopyTree(rhs.root))
{
}

deepCopyTree returns Node*

struct Node
{
    std::string value = "";
    Node *left = nullptr;
    Node *right = nullptr;
};

Deconstructor:

BST::~BST()
{
    DeleteTree(this->root);
}

void DeleteTree(Node* root)
{
    if (root)
    {
        DeleteTree(root->left);
        DeleteTree(root->right);
        delete root;
    }
}

Advice -- Instead of implementing the assignment operator, implement the copy constructor first. Once you do that, the assignment operator becomes trivial by using the [copy / swap idiom](https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom). If you have implemented the copy constructor, please post it, as it could lead to the answer you're looking for using the aforementioned idiom. — PaulMcKenzie, Mar 18 '19 at 22:26
`BST tree1; BST tree2 = tree1;` -- Make that work first (implement the copy constructor). Once you have that working, the 10 hours you spent would be reduced to 5 minutes implementing the assignment operator (probably less than 5 minutes). — PaulMcKenzie, Mar 18 '19 at 22:33
You will need to post the BST class declaration also, to see what the other member variables are (besides `root`). — PaulMcKenzie, Mar 18 '19 at 22:34
ok, so `root` is the only member variable in BST? Also, you need a working BST destructor. Do you have that? — PaulMcKenzie, Mar 18 '19 at 22:35
I did something with the Deconstructor which I am not exactly shure if it is right I am posting it now @PaulMcKenzie — Mihail Yonchev, Mar 18 '19 at 22:39
See my answer. It requires that you have a working copy constructor and destructor. — PaulMcKenzie, Mar 18 '19 at 22:46

PaulMcKenzie · Accepted Answer · 2019-03-18T22:53:37.587

Provided that the copy constructor and destructor for BST work correctly (and that the copy constructor does not use the assignment operator), the BST assignment operator can be easily written using the copy/swap idiom:

#include <algorithm>
//...
BST& BST::operator=(const BST &rhs) 
{
    if ( &rhs != this )  // for optimization purposes, check for self assignment
    {
        BST temp(rhs);  // copy the rhs (uses copy constructor)
        std::swap(temp.root, root);  // swap out the members (root with temp.root)
    } // temp now dies off with the old data (uses destructor)
    return *this;   
}

Note that all we did was create a temporary (which is why the copy constructor has to work properly). Then swap out the this members with the temporary's members. Once this is done, when temp is destroyed, it takes the old data with it (which is why the destructor has to work properly).

If there are more members, then you need to swap those out also (I am assuming the only member variable in BST is root).

So you basically had the solution, just that you didn't realize it (and spent 10 hours for little gain). — PaulMcKenzie, Mar 18 '19 at 22:51

Binary Tree Assignment Operator Overload Problem C++

1 Answers1