C Program to Delete a Binary Tree using Recursion

  • Write a program in C to delete a binary tree using recursion.
  • How to delete all nodes of a binary tree.

Given a binary tree, we have to delete a binary tree. Here we will use recursion to delete all nodes of a binary tree one by one. We will traverse the tree by using post Order traversal because we have to delete all child nodes first before deleting root node. If we delete root node first then we cannot traverse child nodes of root without maintaining a separate data store.

Algorithm to delete a binary tree
Let "root" be the pointer to the root node of binary tree to be deleted.
  • Recursion termination condition : If root is equal to NULL, return.
  • Recursively, delete left sub tree.
  • Recursively, delete right sub tree.
  • Delete root node.

In this program, we will use a user defined recursive function "deleteTree" which takes root node of binary tree to be deleted and deletes all nodes of tree one by one using post Order traversal. 

/*
 First recursively deletes left and right subtree 
 then delete root node 
*/
void deleteTree(struct node *root){
    if(root == NULL)
        return;
    /* Delete Left sub-tree */
    deleteTree(root->left);
    /* Delete right sub-tree */
    deleteTree(root->right);
    
    /* At last, delete root node */
    printf("Deleteing Node : %d\n", root->data);
    free(root);
    
    return;
}

C program to delete a binary tree using pre Order traversal

#include <stdio.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below 
            1
           / \
         2    3
        / \  / \
       4  5 6  7
      /
     8
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);
 
    root->left->left->left = getNewNode(8);
    
    return root;
}

/*
 First recursively deletes left and right subtree 
 then delete root node 
*/
void deleteTree(struct node *root){
    if(root == NULL)
        return;
    /* Delete Left sub-tree */
    deleteTree(root->left);
    /* Delete right sub-tree */
    deleteTree(root->right);
    
    /* At last, delete root node */
    printf("Deleteing Node : %d\n", root->data);
    free(root);
    
    return;
}

int main() {
    struct node *root = generateBTree();    
    
    /* Deleting tree */
    deleteTree(root);
    
    getchar();
    return 0; 
}
Output
Deleteing Node : 8
Deleteing Node : 4
Deleteing Node : 5
Deleteing Node : 2
Deleteing Node : 6
Deleteing Node : 7
Deleteing Node : 3
Deleteing Node : 1
Posted by
Labels: