How to delete a binary search tree from memory?

Question

I have a BST which is a linked list in C++. How would I delete the whole thing from memory? Would it be done from a class function?

Answer 1

Perform a post-order traversal of the tree (i.e. visiting children before parents), and delete each node as you visit it.

Whether or not this has anything to do with classes depends entirely on your implementation.

Answer 2

With the limited information provided ....

If you allocated the nodes with new or malloc (or related functions) than you need to traverse over all the nodes and free or delete them.

An alternative is to put shared_ptr's (and weak_ptr's to kill cyclics) in your allocations -- provided you do it correctly you won't have to free the nodes manually

If you used a quality implementation that you picked up on the internet than provided the classes don't leak, you don't have to worry about anything.

Answer 3

Just delete the children:

struct TreeNode {
    TreeNode *l, *r, *parent;
    Data d;

    TreeNode( TreeNode *p ) { l = 0; r = 0; parent = p }
    TreeNode( TreeNode const & ){ throw logic_error( "can't copy TreeNode" ); }
    ~TreeNode() {
         delete l; // delete does nothing if ptr is 0
         delete r; // or recurses if there's an object
    }
};

or if you're using auto_ptr or some such, that's not even needed:

struct TreeNode {
    auto_ptr< TreeNode > l, r;
    TreeNode *parent;
    Data d;

    TreeNode( TreeNode *p ) { parent = p; }
    TreeNode( TreeNode const & ){ throw logic_error( "can't copy TreeNode" ); }
    //~TreeNode() {}
};

Answer 4

Use smart pointers and forget about it.

Answer 5

If you have access to the linked list itself, it's a piece of cake:

// Making liberal assumptions about the kind of naming / coding conventions that might have been used...
ListNode *currentNode = rootNode;

while(currentNode != NULL)
{
    ListNode *nextNode = currentNode->Next;
    delete currentNode;
    currentNode = nextNode;
}

rootNode = NULL;

If this is a custom implemention of a BST, then this may well be how it works internally, if it has tied itself to a particular data structure.

If you don't have access to the internals, then Potatoswatter's answer should be spot on. Assuming the BST is setup as they suggest, then simply deleting the root node should automatically delete all the allocated memory as each parent down the tree will delete its children.

If you are asking how to go about iterating across a binary tree manually, then you would do the following recursive step:

void DeleteChildren(BSTNode *node)
{
    // Recurse left down the tree...
    if(node->HasLeftChild()) DeleteChildren(node->GetLeftChild());
    // Recurse right down the tree...
    if(node->HasRightChild()) DeleteChildren(node->GetRightChild());

    // Clean up the data at this node.
    node->ClearData(); // assume deletes internal data

    // Free memory used by the node itself.
    delete node;
}

// Call this from external code.
DeleteChildren(rootNode);

I hope I've not missed the point here and that something of this helps.