Delete given Binary Tree | Iterative & Recursive

Given a binary tree, write an efficient algorithm to delete entire binary tree.

 
The program should de-allocate every single node present in the tree, not just change reference of the root node to null.
 


 

The idea is to traverse the tree in post-order fashion and delete left and right subtree of a node before deleting the node itself. Note that we cannot traverse the tree in preorder or inorder fashion as we can’t delete a parent before deleting its children’s.

 
C++ implementation –
 

Download   Run Complete Code

 


 
Iterative solution –
 

In iterative version, we perform level order traversal of the tree. The idea is to delete each node in the queue one by one after pushing their children to the queue. Note that we’re deleting a parent here before deleting its children’s as we’re pushing them into the queue and they will be processed and deleted afterwards.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of both recursive and iterative solution is O(n).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂