Time Complexity : O(n)
Space Complexity :O(1)
Here we use, Post-Order traversal method to delete the tree nodes. Because, before deleting the parent node we should delete children nodes.
Example
Figure : Binary tree
If we apply Treedelete(A),
The order of deletion of nodes is: F, G, D, E, B, H, I, C,
Algorithm
Step 1 : we create a delete tree function. which deletes any sub-tree you want to delete.
Step 2 : In this we use post-order traversal recursive method, but instead of printing the node when we visit it, we delete it.
a)Â Â Â Â We use free(node) to delete the node.
b)Â Â Â While deleting we print that we are deleting the particular node.
Step 3 : we make the root null after deleting the whole tree. Because, if user try to access the values without making to null it causes problems using root pointer.
C++ Program
/* code for deletion of a tree*/ #include <bits/stdc++.h> #include <stdio.h> #include <stdlib.h> using namespace std; /* implementation of the binary tree with pointers to left child node and right child node*/ struct node { char data; struct node* left; struct node* right; }; /*In this function we are creating a node with the given data and null left and right pointers */ struct node* CreateNewNode(char data) { struct node* node = (struct node*)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /*This is the recursive function for Postorder traversal*/ void PostorderTraversal(struct node* node) { if (node == NULL) return; PostorderTraversal(node->left);/*Recrsion on Left sub-tree*/ PostorderTraversal(node->right); /*Recursion on Right sub-tree*/ printf("%c ", node->data); /*printing data of the node*/ } /*Deleting Tree in Post-Order Traversal method */ void TreeDelete(struct node* node) { if (node == NULL){ return; } TreeDelete(node->left);//deleting left subtree TreeDelete(node->right);//deleting right subtree printf("\n Deleting node: %c", node->data); free(node);//deleting the node } /*Main function*/ int main() { /*Here we are creating a tree by inserting elements*/ struct node *root = CreateNewNode('A'); root->left = CreateNewNode('B'); root->right = CreateNewNode('C'); root->right->left = CreateNewNode('H'); root->right->right = CreateNewNode('I'); root->left->left = CreateNewNode('D'); root->left->left->left = CreateNewNode('F'); root->left->left->right = CreateNewNode('G'); root->left->right = CreateNewNode('E'); cout<<"Post-order traversal of the given input binary tree is :"; /*Printing the tree using Post-order Traversal*/ PostorderTraversal(root); cout<<"\n"; /*deleting the whole tree*/ cout<< " Deleting Tree.......! " ; TreeDelete(root); root = NULL; cout<<"\n"; cout<< " Tree Deleted!! " ; return 0; }