# How to delete a binary search tree from memory?

### Tags:

#### binary-tree

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? 245 asked Feb 27 '23 21:02

#### neuromancer

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;
};
`````` 179 answered Mar 02 '23 18:03

#### Potatoswatter

``````// 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. 36 answered Mar 02 '23 18:03