TOPIC: C++ program to delete an entire binary tree.
Link to source code: https://github.com/pyskmr/D4datastructures/blob/master/binary%20tree/deleteBinayTree.cpp
DESCRIPTION:
There are 3 recursive methods by which we can easily achieve our goal and these 3 methods come under DFS that are: 
1.INORDER
2.POSTORDER
3.PREORDER
Note:  I have described POSTORDER approach in my previous article, go check that out
But still, I'm explaining in a brief how these traversing works in these approaches.
1. INORDER:  Left Subtree, root, Right Subtree
2. PREORDER:  root, Left Subtree, Right Subtree
3. POSTORDER:  Left Subtree, Right Subtree, root
And at each recursive approach, the basis or the terminating or the base case will be when the root visited becomes NULL.
Today we will be focussing on POSTORDER approach as we have discussed before so it will be easier to understand but still, I will try to brush up the points. Let's look at the algorithm first.
PROCEDURE DEL_TREE
Case 1. If the root is NULL that is there is no node to delete.
Return
Case 2. Call this procedure to the left subtree of the root.
Call this procedure to the right subtree of the root.
Delete root.
NOTE: In case of preorder and e inorder we have to maintain copy(ies) of pointers to left and right subtree root. That is why we prefer postorder approach more because it is space friendly.
Now let's see an example just to make things clearer.
Initially, the root will be 10 so our call stack will be following.

Now left subtree node 3 will be root
And it will also call left subtree and right subtree but both are NULL so they will return
And 3 will get deleted.

Now the right subtree of 10 will be visited
Which further have two child 2 (left) and 1 (right), so we will visit 2 first
Since 2 has no child so both of the left and right call will return and then 2 will be deleted.

It also does'nt have further child so both calls(left and right) will return and 1 will be deleted.
6 will be deleted then.
At last 10 will also get deleted and the control will go back to the main.
Complexity
complexity will be O(n) because we are traversing each node only once (applicable on INORDER, PREORDER also).
CODE:
1  #include<iostream>

Comments