views:

228

answers:

5
+4  A: 

Is this the correct way to implement the default constructor?

No, calling delete on something that has not been allocated using new invokes Undefined Behavior (in most cases it results to crash of your application)

Set your pointers to NULL in your default constructor.

TreeNode::TreeNode(){
  data = "";   //not required since data being a std::string is default initialized.
  left = NULL;
  right = NULL;   
}

I don't see such problems with the rest of your code. Your assignment operator shallow copies the nodes whereas your copy constructor deep copies them.

Follow a suitable approach as per your requirement. :-)

EDIT:

Instead of assigning pointers in your default constructor use an initialization list

Prasoon Saurav
Thanks. What about other questions?
Michael Sync
See the edits, I have tried to answer your questions briefly. :-)
Prasoon Saurav
Thanks .. Do I have to put "left = new TreeNode();" in copy constructor? Is it necessary? Otherwise, I will remove it...
Michael Sync
@Michael : Depends on whether you want to perform [deep copy or shallow copy](http://en.wikipedia.org/wiki/Object_copy#Another_example_of_deep_and_shallow_copying_in_C.2B.2B)
Prasoon Saurav
AFAIK, using copy constructor is for deep-copy, right? so, I would say that I want deep-copy..
Michael Sync
one more thing. Do I need to add the logic for comparing the object in operatior=?
Michael Sync
@Michael : You would have to add code to check [self assignment](http://www.parashift.com/c++-faq-lite/assignment-operators.html#faq-12.1).
Prasoon Saurav
+7  A: 

Even better, I think

 TreeNode::TreeNode():left(NULL), right(NULL)
 {
   // data is already set to "" if it is std::string
 }

plus you have to delete the pointers 'left' and 'right' in the assignment operation, or you'll have a memory leak

frag
+1 from me for mentioning initialization list.
Prasoon Saurav
+11  A: 

Am I correct in saying that I need to delete the pointer in destructor?

Whenever designing an object like this, you first need to answer the question: Does the object own the memory pointed to by that pointer? If yes, then obviously the object's destructor needs to clean up that memory, so yes it needs to call delete. And this seems to be your intent with the given code.

However in some cases, you might want to have pointers that refer to other objects whose lifetime is supposed to be managed by something else. In that case you don't want to call delete because it is the duty of some other part of the program to do so. Furthermore, that changes all the subsequent design that goes into the copy constructor and assignment operator.

I'll proceed with answering the rest of the questions under the assumption that you do want each TreeNode object to have ownership of the left and right objects.

Is this the correct way to implement the default constructor?

No. You need to initialize the left and right pointers to NULL (or 0 if you prefer). This is necessary because unintialized pointers could have any arbitrary value. If your code ever default constructs a TreeNode and then destroys it without ever assigning anything to those pointers, then delete would be called on whatever that initial value is. So in this design, if those pointers aren't pointing at anything, then you must guarantee that they are set to NULL.

How to assign the pointer variable in the copy constructor? The way that I wrote in Copy Constructor might be wrong.

The line left = new TreeNode(); creates a new TreeNode object and sets left to point to it. The line left = node.left; reassigns that pointer to point to whatever TreeNode object node.left points to. There are two problems with that.

Problem 1: Nothing now points to that new TreeNode. It is lost and becomes a memory leak because nothing can ever destroy it.

Problem 2: Now both left and node.left end up pointing to the same TreeNode. That means the object being copy constructed and the object it's taking values from will both think they own that same TreeNode and will both call delete on it in their destructors. Calling delete twice on the same object is always a bug and will cause problems (including possibly crashes or memory corruption).

Since each TreeNode owns its left and right nodes, then probably the most reasonable thing to do is make copies. So you would write something similar to:

TreeNode::TreeNode(const TreeNode& node)
    : left(NULL), right(NULL)
{
    data = node.data;

    if(node.left)
        left = new TreeNode(*node.left);
    if(node.right)
        right = new TreeNode(*node.right);
}

Do I need to implement the same code (except return ) for both copy constructor and operatior=?

Almost certainly. Or at least, the code in each should have the same end result. It would be very confusing if copy construction and assignment had different effects.

EDIT - The above paragraph should be: The code in each should have the same end result in that the data is copied from the other object. This will often involve very similar code. However, the assignment operator probably needs to check if anything has already been assigned to left and right and so clean those up. As a consequence, it may also need to watch out for self-assignment or else be written in a way that doesn't cause anything bad to happen during self-assignment.

In fact, there are ways to implement one using the other so that the actual code that manipulates the member variables is only written in one place. Other questions on SO have discussed that, such as this one.

TheUndeadFish
How were you the only one to point out the `new TreeNode();` memory leak?
Evan Huddleston
+1 for understanding the problem and giving a good solution. This answer is definitely better than that of mine. :)
Prasoon Saurav
Thank you so much for very detailed answer..
Michael Sync
Before assigning to `left` you should probably delete the old value (dito for `right`)
Martin York
Oh right, I totally forgot about the assignment operator needing to watch out for and properly clean up anything previously assigned to `left` and `right`.
TheUndeadFish
+1  A: 

May I also suggest boost::shared_ptr from the library boost (if you can used it), instead of simple pointers? It'll solve a lot of problems you might have with invalid pointers, deep copies e.t.c.

frag
indeed, you'll run into trouble with the code as it is when you assign one tree node from another and then both are deleted: the children will be deleted twice but were only allocated once. So I can only support this suggestion to use smart pointers.
Andre Holzner
+1  A: 

This is how I would do it:
Because you are managing two resources in the same object doing this correctly becomes a bit more complex (Which is why I recommend never managing more than one resource in an object). If you use the copy/swap idiom then the complexity is limited to the copy constructor (which is non trivial to get correct for the strong exception guarantee).

TreeNode::TreeNode()
    :left(NULL)
    ,right(NULL)
{}

/*
 * Use the copy and swap idium
 * Note: The parameter is by value to auto generate the copy.
 *       The copy uses the copy constructor above where the complex code is.
 *       Then the swap means that we release this tree correctly.
 */ 
TreeNode& TreeNode::operator= (const TreeNode node)
{
     std::swap(data,  node.data);
     std::swap(left,  node.left);
     std::swap(right, node.right);
     return *this;
}

TreeNode::~TreeNode()
{
     delete left;
     delete right;
}

The hard part now:

/*
 * The copy constructor is a bit harder than normal.
 * This is because you want to provide the `Strong Exception Guarantee`
 * If something goes wrong you definitely don't want the object to be
 * in some indeterminate state.
 *
 * Simplified this a bit. Do the work that can generate an exception first.
 * Once all this has been completed we can do the work that will not throw.
 */   
TreeNode::TreeNode(const TreeNode& node)
{
    // Do throwable work.
    std::auto_ptr<TreeNode>  nL(node.left  == null ? null : new TreeNode(*node.left));
    std::auto_ptr<TreeNode>  nR(node.right == null ? null : new TreeNode(*node.right));

    // All work that can throw has been completed.
    // So now set the current node with the correct values.
    data  = node.data;
    left  = nL.release();
    right = nR.release();
}
Martin York
+1 Even if this might be a bit advanced for someone just learning the basics of managing pointers and implementing the big three operators, this is still a correct "industrial-strength" solution.
TheUndeadFish
@TheUndeadFish: It is only complex because there are two resources in the object to manage. If it was a single resource there would be basically zero code required (Which is why IMHO objects should only manage one resource at a time).
Martin York
Thanks a lot, Martin.. I will try to compile it at my end.. I'm using MinGW.... I didn't use auto_ptr and release() before.. I think the reason why I need two objects is that I need to have left node and right node ....
Michael Sync
@Michael Sync: Simplified the copy constructor a bit.
Martin York