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

Just delete the children:

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

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

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

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

    TreeNode( TreeNode *p ) { l = nullptr; r = nullptr; parent = p; }
    TreeNode( TreeNode const & ) = delete;
    ~TreeNode() = default;
};

Answer 2

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.