Delete Binary Tree

Delete Binary Tree” is an elementary problem based on tree data structure. Here, we are given a binary tree and our task is to delete given binary tree. We need to delete all the nodes and release memory.

If tree needs to be deleted, then, it needs to be traversed first and one-by-one memory of all the nodes must be released. It’s obvious that before deleting any parent node, we need to delete child node. So, for that, postorder traversal can be used, as it will help to delete left child, then right child and in last root node.

C++ Program to Delete Binary Tree is as follows:

/* C++ Program to Delete Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Delete Binary Tree */
void deleteTree(Node *root)
{
   /* Base Case */
   if(root == NULL)
   return;
   
   deleteTree(root -> left);
   deleteTree(root -> right);
   
   cout<<"Deleting Node with Value "<<root->data<<"\n";
   delete root;
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to delete binary tree */
    deleteTree(root);
}

OUTPUT:

Deleting Node with Value 4
Deleting Node with Value 8
Deleting Node with Value 5
Deleting Node with Value 2
Deleting Node with Value 9
Deleting Node with Value 6
Deleting Node with Value 7
Deleting Node with Value 3
Deleting Node with Value 1

Method 2: Deletion using Level Order Traversal

We can delete the given binary tree using level order traversal also. In the previous method, we delete the leaf nodes first and then their parents. But, here, we will delete the tree in root to leaf fashion.

Before deleting any node, we will push the left and right child of it, if exist, into queue.

C++ Program to Delete Binary Tree is as follows:

/* C++ Program to Delete Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Delete Binary Tree */
void deleteTree(Node *root)
{
   /* Base Case */
   if(root == NULL)
   return;
   
   queue<Node *> que;
   
   que.push(root);
   
   while(!que.empty())
   {
       Node *temp = que.front();
       que.pop();
       
       if(temp -> left)
       que.push(temp -> left);
       
       if(temp -> right)
       que.push(temp -> right);
       
       cout<<"Deleting Node with Value "<<temp -> data<<"\n";
       delete temp;
   }
   
   root = NULL;
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to delete binary tree */
    deleteTree(root);
}

OUTPUT:

Deleting Node with Value 1
Deleting Node with Value 2
Deleting Node with Value 3
Deleting Node with Value 4
Deleting Node with Value 5
Deleting Node with Value 6
Deleting Node with Value 7
Deleting Node with Value 8
Deleting Node with Value 9

Related Posts:

  1. Introduction to Tree Data Structure
  2. Binary Tree Traversals
  3. Print All Leaf Nodes of a Binary Tree
  4. Count Number of Nodes in a Binary Tree
  5. Print Alternate Levels of Binary Tree
  6. Maximum Width of Binary Tree
  7. Level Order Tree Traversal
  8. Left View of Binary Tree
  9. Right View of Binary Tree
  10. Compute Height of Binary Tree
  11. Inorder Tree Traversal Using Stack
  12. Preorder Tree Trasversal Using Stack
  13. Postorder Tree Traversal Using Stack
  14. Vertical Order Tree Traversal
  15. Top View of Binary Tree
  16. Bottom View of Binary Tree
  17. Check if two trees are mirror Trees of Each Other
  18. Convert Binary Tree to its Mirror Tree
  19. Check if Binary Tree is Symmetric or Not
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...