Delete a Binary Tree with a Stack

Question

I'm still working on my binary trees, and the insertion, lookup, maximum, minimum functions are all working great so far. So I want to do a deletion function next. I included a Stack which saves- ah hell, I'll just show the code:

class Tree
{
private:
    int value_;
    Tree *root_;
    Tree *left_;
    Tree *right_;

    std::stack<Tree*> treeStack;

The delete function:

int Tree::eraseTree()
{
    while( !treeStack.empty() )
    {
        Tree *temp = treeStack.top();
        treeStack.pop();
        delete temp;
    }
    if( treeStack.empty() )
        return 1;
    else
        return -1;
}

I'm getting errors now. This wouldn't be much of a problem- I try to debug my own code- except this time it's telling me there is an error in the <deque> library file which I am not even using.

Before the program shuts off I get System.AccessViolationException and the faulty code points to the deque file. Of course it can't be there, it has to be some pointer in my code. Which leads me to believe I am not working the stack correctly, or not pushing to the stack correctly.

What am I doing wrong here? Am I actually deleting the nodes when I call .pop on the stack?

EDIT:

if( !root_ )
{
    root_ = new Tree(val, 0, 0);
    treeStack.push(root_);
    return val;
}

And

Tree *parent = findInsertionPoint(val, root_);
    if( val < parent->value_ )
        parent->left_  = new Tree(val, 0, 0);
    else
        parent->right_ = new Tree(val, 0,0);

    treeStack.push(parent);
    return val;

Is where I am pushing my elements on the stack.

Additional Question: Does a std::stack have to be built in the ctor?

Answer 1

It sounds like you might be deleting something twice.

Make sure the stuff you're deleting isn't used or deleted anywhere else, especially after calling your eraseTree() method.

Answer 2

Change root_*, left_* and right_* into auto_ptrs to guarantee their destruction. Then when you come to delete a node, you can just delete root_.release(); and all is fine. Gotta ask why you're using a stack.

Answer 3

You're crashing in deque because the stack contains one of those. If you look at the stack trace after the crash, then you can find out what your code was doing when it happened.

It looks like the final snippet of code is putting the wrong node on the stack; surely it should be the newly created node, not the insertion point? If you add two nodes to a parent, then the parent will end up in the stack twice, and will be deleted twice.

It should probably be more like

Tree *parent = findInsertionPoint(val, root_);
Tree *child = new Tree(val, 0, 0);
if( val < parent->value_ )
    parent->left_  = child;
else
    parent->right_ = child;

treeStack.push(child);
return val;

But I'd favour DeadMGs suggestion to use smart pointers for left_ and right_ (but don't make root_ an auto_ptr, if that's shared by all the nodes), and let them clean up for you. I'm not sure I see the point of the stack; if it's to speed up the tree's destruction, then ask yourself two questions before adding a complex and error-prone optimisation:

• is it slow enough to be worth the development/debugging cost of optimising?
• is it worth the extra runtime and memory cost of building and maintaining the stack alongside the tree?

And your additional question: the stack will be built in the constructor, but you don't have to write any code to do it. Its default constructor will be called automatically, and that will give you a usable, empty stack.

Also, unless this is a learning exercise, you should use std::multiset rather than reinventing it.

Answer 4

You got an error in deque because by default std::stack uses this class as an internal container. Look at the stack definition:

template<class _Ty, class _Container = deque<_Ty> > class stack;