Non-recursive program to delete an entire binary tree. - GeeksforGeeks
Now how to delete an entire tree without using recursion. This could easily be done with the help of Level Order Tree Traversal. The idea is for each dequeued node from the queue, delete it after queuing its left and right nodes (if any). The solution will work as we are traverse all the nodes of the tree level by level from top to bottom, and before deleting the parent node, we are storing its children into queue that will be deleted later.
Read full article from Non-recursive program to delete an entire binary tree. - GeeksforGeeks
Now how to delete an entire tree without using recursion. This could easily be done with the help of Level Order Tree Traversal. The idea is for each dequeued node from the queue, delete it after queuing its left and right nodes (if any). The solution will work as we are traverse all the nodes of the tree level by level from top to bottom, and before deleting the parent node, we are storing its children into queue that will be deleted later.
void
_deleteTree(Node *root)
{
// Base Case
if
(root == NULL)
return
;
// Create an empty queue for level order traversal
queue<Node *> q;
// Do level order traversal starting from root
q.push(root);
while
(!q.empty())
{
Node *node = q.front();
q.pop();
if
(node->left != NULL)
q.push(node->left);
if
(node->right != NULL)
q.push(node->right);
free
(node);
}
}
def
_deleteTree(root):
# Base Case
if
root
is
None
:
return
# Create a empty queue for level order traversal
q
=
[]
# Do level order traversal starting from root
q.append(root)
while
(
len
(q)>
0
):
node
=
q.pop(
0
)
if
node.left
is
not
None
:
q.append(node.left)
if
node.right
is
not
None
:
q.append(node.right)
node
=
None
return
node
# Deletes a tree and sets the root as None
def
deleteTree(node_ref):
node_ref
=
_deleteTree(node_ref)
return
node_ref