CODEWITHSUNDEEP
c++dynamicrecursionavl-tree
Syntactic Fructose
Syntactic Fructose

Reputation: 20076

Destroy entire AVL tree

I'm having a problem entirely deleting my AVL tree. I've figured out how to delete just a single node, but my destroyTree function doesn't seem to actually destroy every node recursively. What could I be doing wrong?

I have a struct nodeType<myType>

template <class myType>
struct nodeType {
  myType keyValue;
  int nodeHeight;
  nodeType<myType> *left;
  nodeType<myType> *right;
};

and I am attempted to delete all existing nodes with:

  if(node != NULL) {
    destroyTree(node->left);
    destroyTree(node->right);
    delete node;
  }
  node = NULL;

but this does not seem to properly delete the nodes, when checking for the height it still gives me the height before the destroy was called although crashes when attempting to print. In the main function calling destroy tree I used a simple if statement

template <class myType>
void avlTree<myType>::destroyTree()
{
  destroyTree(root);
  if(root == NULL)
    std::cout << "destroyed" << std::endl;
}

shows that root is NOT null (yes is not printed)

Upvotes: 1

Views: 2710

Answers (2)

Steve Lorimer
Steve Lorimer

Reputation: 28659

I'm guessing you're not taking node by reference, and therefore when you set the node to NULL you're actually setting a local copy of the node to null.

Won't work because root is taken by value - will have prior value after function call:

template <class myType>
void avlTree<myType>::destroyTree(nodeType<myType>* node) // note node taken by value here
{
  if(node != NULL) {
    destroyTree(node->left);
    destroyTree(node->right);
    delete node;
  }
  node = NULL;
}

Will work because root is taken by reference - will be null after the function call:

template <class myType>
void avlTree<myType>::destroyTree(nodeType<myType>* &node) // note node taken by reference here
{
  if(node != NULL) {
    destroyTree(node->left);
    destroyTree(node->right);
    delete node;
  }
  node = NULL;
}

Upvotes: 2

Amadeus
Amadeus

Reputation: 10655

Look at this piece of code:

destroyTree(root);
if(root == NULL)
    std::cout << "destroyed" << std::endl;

Probably your destroyTree function has this prototype:

void destroyTree(nodeType<myType> *node);

The problem is that node cant update the caller memory address, but only the contents that caller is pointing. This means that root will never be update, i.e., its contents cant be updated to NULL.

To do that, you need a prototype that is something like that:

void destroyTree(nodeType<myType> **node);

Upvotes: 3

Related Questions