We have already discussed binary trees and binary search trees in previous posts. In this article, we will formulate an algorithm to Delete a Binary Tree without causing a memory leak. We will also implement the algorithm in Python.
What is memory leak?
Memory leak in a program occurs when we allocate memory to a variable and forget to delete it. Memory leaks can cause problems in terminating the programs. So, it is necessary to delete an allocation before removing the reference to the memory.
Python handles these errors using garbage collection procedures but we should be careful to not write code that can cause memory leaks in our programs. Here we will discuss an algorithm to delete an entire binary tree without causing a memory leak.
How to delete nodes of binary tree without memory leak?
To delete the elements of the binary tree, we can use the del statement to free the memory allocated to each node. Also, to avoid memory leaks, we will have to delete the children of a node before deleting the node itself. In this way, we can make sure that variables having reference to a node will never be deleted before freeing the memory.
To traverse the whole tree, we can use any tree traversal algorithm such as in-order, pre-order, level-order, or post-order tree traversal algorithm. But, we will need to traverse the children of a node before the parent as the children nodes have to be deleted before the parent node to avoid memory leak.
In the post-order tree traversal algorithm, we traverse the children of any node before visiting the parent node. So, we will use the post-order tree traversal to implement the algorithm to delete a binary tree. In the next section, we will modify the post-order tree traversal algorithm to implement the algorithm.
Algorithm for deleting the binary tree
As discussed above, the algorithm for deleting a binary tree can be formulated as follows.
- Start from the root.
- Check if the current node is None, If yes, return. Else go to 3.
- Recursively delete the left child of the current node.
- Recursively delete the right child of the current node.
- Delete the current node.
Deleting a Binary Tree in Python
As we have discussed and formulated the algorithm to delete a binary tree, we will implement it in python. We will also execute the algorithm for the binary tree given in the following image. In the output, you can verify that each node is deleted before the deletion of its parent.
Code:
from queue import Queue
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def insert(root, newValue):
# if binary search tree is empty, make a new node and declare it as root
if root is None:
root = BinaryTreeNode(newValue)
return root
# binary search tree is not empty, so we will insert it into the tree
# if newValue is less than value of data in root, add it to left subtree and proceed recursively
if newValue < root.data:
root.leftChild = insert(root.leftChild, newValue)
else:
# if newValue is greater than value of data in root, add it to right subtree and proceed recursively
root.rightChild = insert(root.rightChild, newValue)
return root
def deleteTree(root):
if root:
# delete left subtree
deleteTree(root.leftChild)
# delete right subtree
deleteTree(root.rightChild)
# traverse root
print("Deleting Node:", root.data)
del root
root = insert(None, 15)
insert(root, 10)
insert(root, 25)
insert(root, 6)
insert(root, 14)
insert(root, 20)
insert(root, 60)
print("deleting all the elements of the binary tree.")
deleteTree(root)
Output:
deleting all the elements of the binary tree.
Deleting Node: 6
Deleting Node: 14
Deleting Node: 10
Deleting Node: 20
Deleting Node: 60
Deleting Node: 25
Deleting Node: 15
Conclusion
In this article, we have discussed the algorithm to delete a binary tree by using a modified post-order tree traversal algorithm. Stay tuned for more articles on the implementation of different algorithms in Python.