Why does my C++ code fail to delete all nodes in my BST?

Question

This is supposed to traverse a BST and delete every node, including the root node. However, at the end, I get the message "root still has a left node." Why aren't all nodes deleted?

void deleteTree()
{   
    deleteNode(root);
    if(root->right)
        cout << "root still has a right node" << endl;
    if(root->left)
        cout << "root still has a left node" << endl;
    root = 0;

}   

void deleteNode(node *p) 
{   
    if(p->left) 
    {   
        deleteNode(p->left);
        p->left = 0;
    }   
    if(p->right) 
    {   
        deleteNode(p->right);
        p->right = 0;
    }   

    cout << "Deleting node containing " << p->data << endl;
    delete p;
}   

Answer 1

Your are deleting p at the end (root) and then trying to access its contents in deleteTree(), where root no longer points to allocated memory. The result is going to be undefined.

Answer 2

You're deleting root. And then your code is trying to access memory where it was.

You're well into undefined-behaviour land there.

Answer 3

You should not dereference root after you delete it in deleteNode. Use a debugger to inspect why root->left is non-null.

Answer 4

You are looking at root->left after you've already deleted root, making it avalable for use in a new allocated block.

Answer 5

I would simply change the tree itself, it would be easier to deal with it then:

struct Node
{
  Node(data_type data): mLeft(), mRight(), mData(data) {}
  Node(const Node& rhs): mLeft(), mRight(), mData(rhs.mData)
  {
    if (rhs.mLeft.get()) mLeft.reset(new Node(*rhs.mLeft));
    if (rhs.right.get()) mRight.reset(new Node(*rhs.mRight));
  }
  Node& operator=(Node rhs)
  {
    this->swap(rhs);
    return *this;
  }
  ~Node() { }

  void swap(Node& rhs)
  {
    using std::swap;
    swap(mLeft, rhs.mLeft);
    swap(mRight, rhs.mRight);
    swap(mData, rhs.mData);
  }

  Node* left() const { return mLeft.get(); }
  void left(std::auto_ptr<Node> node) { mLeft= node; }

  Node* right() const { return mRight.get(); }
  void right(std::auto_ptr<Node> node) { mRight = node; }

  data_type& data() { return mData; }
  const data_type& data() const { return mData; }

private:
  std::auto_ptr<Node> mLeft;
  std::auto_ptr<Node> mRight;
  data_type mData;
};

By being Object-Oriented, each Node is now responsible for the memory it handles. Also, using std::auto_ptr in the interface makes it clear that it takes ownership.

Note that it's been tailored for deep-copying, any other approach requiring boost::shared_ptr or equivalent. And yes std::auto_ptr leaves you dealing with copying by yourself, no magic there.

This design is much cleaner than using a plain C-struct with everyone being able to manipulate the resources. You still have full access to the underlying data via the accessor... but THEY take care not to invoke undefined behavior...

Of course, you can still crash it down:

Node& node = ...
delete node.left(); // haha

But if C++ may protect against unintended issues, it leaves the door open to evil code.