Delete a 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).
 

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)
Loading...

 
Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of