Delete a binary tree

Question:

Given a binary tree root node, delete that tree

Example:

Consider the tree given below. How do you delete it?

Here if you delete root node first, the you will loose link to left and right children.

So we need to user post order traversal.

In Post order traversal, we visit left, right and then root.

Here instead of visiting, we need to delete it.

When a node is given, delete it’s left and right children before deleting the node itself.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

void delete_tree(Node* node)  
{  
    if (node == NULL) 
        return;  
  
    // delete both subtrees
    delete_tree(node->left);  
    delete_tree(node->right);  
      
    // then delete the node 
    cout << "\n Deleting node: " << node->data;  
    delete node; 
}  


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    delete_tree(root); 
    cout<<"\nTree deleted\n " ; 


    return 0;  
}  

Output:

Deleting node: 7
Deleting node: 15
Deleting node: 10
Deleting node: 18
Deleting node: 30
Deleting node: 25
Deleting node: 16
Tree deleted