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)