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.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

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

 I always put an emphasis on coding on your own but I'm still providing you the code just in case you need some help.

CODE:-

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

#include<iostream>

/*

C++ program to delete an entire binary tree.

*/

using namespace std;

/* a base class is created which contain the data of every node in the tree */

template<class P>
class node
{
	public:
		P data;
		node *left,*right;
		node()
		{
			left=NULL;
			right= NULL;
		}
		node(P value)
		{
			data = value;
			left=right=NULL;
		}
};

/* class tree inheriting node class and having a root object of the node as its class member */

template<class C>
class tree:public node<C>
{
	private:
		node<C> *root;
	public:
		tree();
		node<C>* getRoot();
		void createTree();
		void del_tree(node<C> *);
};

/* tree class default constructor.As soon as the object will be made its root will be pointed to NULL */

template<class C>
tree<C> :: tree()
{
	root=NULL;
}

/* this will return the root of the tree's object */

template<class C>
node<C>* tree<C> :: getRoot()
{
	return root;
}

/* this will create the tree in the example we just shown */
template<class C>
void tree<C>::createTree()
{
	root=new node<C>(10);
	
	root->left=new node<C>(3);
	root->right=new node<C>(6);
	root->right->left=new node<C>(-2);
	root->right->right=new node<C>(1);
}

/* Postorder approach to delete the full tree */
template<class C>
void tree<C> :: del_tree(node<C> *r)
{

/* check if the current root is NULL or not*/	
	
	if(r==NULL)
	{
		return;
	}
/* if not then traverse its left and right child and atlast delete the desired node */ 
	else
	{
		del_tree(r->left);
		del_tree(r->right);
		cout<<"\ndeleted	"<<r->data;
		delete(r);
	}
}

int main()
{
	tree<int> obj;
	int value ;
	value=46;
	
	obj.createTree();
	obj.del_tree(obj.getRoot());

	return 0;
}

OUTPUT :-

KEEP UP THE GOOD WORK AND KEEP CODING. (: