# Delete a Binary Tree

By | October 24, 2015

# Program to Delete a Binary Tree.

### Delete a Binary Tree Problem Statement:

Given a binary tree, we need to delete the complete tree.

The root pointer should have a value NULL after the completion of the operation.

This is sometimes called as destructor for binary tree.

### Delete a Binary Tree Example:

The input tree :

```             80
/     \
60      110
/  \    /  \
35   40  85   130```

After the program is run, there should be nothing left.

### Delete a Binary Tree Solution:

Most of the questions that can be made on a binary tree, are/can be directly done/solved using one of the Tree Traversals. Thus, such questions are simple .

In this question, we need to delete the tree.
If we delete the parent before the children, then the pointers pointing to the children will be lost and there will be a memory leak.
Hence, we need to the children before the parent, thus we will follow POSTORDER traversal.

#### Algorithm to Delete a Binary Tree :

1. If the root is null ( the tree is empty ) then return 0.
2. Else
1. Delete the left subtree
Delete(root->left).
2. Delete the right subtree
Delete(root->right).
3. delete the root and print the value deleted.

#### Delete a Binary Tree Solution Code:

Here is the working code:

```#include <bits/stdc++.h>
using namespace std;

/*Structure for each node of the tree*/
struct node
{
int data;
node *right,*left;
};

/*Function that allocates memory for
each new node and initialises it*/
node * newNode(int data)
{
node *temp=new node;
temp->data=data;
temp->left=NULL;
temp->right=NULL;

return temp;
}

/*The function that actually delete
nodes in the tree*/
void Delete(node *root)
{
/*Base case when the tree is NULL*/
if(!root)
return 0;
/*First Recur on Left subtree,
Then Reccur on right subtree
Then Delete the parent */

Delete(root->left);
Delete(root->right);

cout<<"\nDeleted value: "<<root->data;
delete(root);
}

int main()
{
/*
We are making the following tree
80
/     \
60      110
/  \    /  \
35   40  85   130
This is a BST.
*/
node *root         = newNode(80);
root->left         = newNode(60);
root->right        = newNode(110);
root->left->left   = newNode(35);
root->left->right  = newNode(40);
root->right->left  = newNode(85);
root->right->right = newNode(130);

Delete(root);
root=NULL;
cout<<"\nThe tree has been Deleted\n";

return 0;
}```

Output:

```Deleted value: 35
Deleted value: 40
Deleted value: 60
Deleted value: 85
Deleted value: 130
Deleted value: 110
Deleted value: 80
The tree has been Deleted```

Time Complexity: O(N)