Jul 302012
 

Given a binary tree, write code to delete the entire tree. Structure of the node is as given below:

    struct Node
    {
        int data;
        Node* lptr;  // ptr to LEFT sub-tree
        Node* rptr;  // ptr to RIGHT sub-tree
    };


Signature of the function:

The function to delete the tree will take a pointer to the root of the tree. Signature of the function will be

    void deleteTree(Node** root);

To know, why it is a double pointer and not just Node* see this post on changing pointer passed to a function as argument. In this case we will be changing root also (setting it to NULL after the entire tree is deleted).

Deleting all Nodes of Tree

We must traverse all the nodes and delete them one-by-one to delete the entire tree. Hence we need to traverse the tree (visit each node of the tree).

There are three basic traversals of a binary tree, PreOrder, InOrder and PostOrder plus there can be complex traversals like level-wise traversal.

For deleting all the nodes we should use a traversal where left and right subtrees of a node are deleted before deleting the node (If we delete the Node itself before deleting the sub-trees, then we may loose pointer to sub-trees), hence PostOrder traversal makes the obvious choice for deleting Nodes.

Hence, the nodes of the tree given on the right side will be deleted in the following order:

1 4 8 5 40 30 10

We are deleting the child nodes before deleting the node itself.

Code:

    /**  Recursive Function to delete all the nodes of a tree 
     *   pointed to be root.
     */
    void deleteTree(Node* root) 
    {
        if (root == NULL) 
            return;

        // Deleting the Left sub-tree
        deleteTree(root->lptr);

        // Deleting the Right sub-tree
        deleteTree(root->rptr);

        // Now delete the node itself
        free(root);
    }

This function will just delete the tree but will not set the root pointer to NULL (because it is accepting Node* and not Node** as discussed above). So we can have two function

    /**  Delete the tree and set the root to NULL
     */
    void deleteTree(Node** ptrRoot)
    {
        if(ptrRoot == NULL || *ptrRoot == NULL)
            return;

        deleteTreeRecursive(*ptrRoot);
        ptrRoot = NULL;
    } 

    /**  Recursive Function to delete all the nodes of a tree 
     *   pointed to be root.
     */
    void deleteTreeRecursive(Node* root) 
    {
        if (root == NULL) 
            return;

        // Deleting the Left sub-tree
        deleteTree(root->lptr);

        // Deleting the Right sub-tree
        deleteTree(root->rptr);

        // Now delete the node itself
        free(root);
    }

Note that if we print the data of the Node before deleting it, then the values will be printed in post-order traversal.

Time Complexity: O(n)

  One Response to “deleting a tree”

Comments (1)
  1. DeleteTree(struct node *p)
    {
    if(p != NULL)
    {
    if(p->left == NULL && p->right == NULL)
    {
    printf(“Deleting node %d\n”,p->value);
    free(p);
    }
    else
    {
    DeleteTree(p->left);
    p->left=NULL;
    DeleteTree(p->right);
    p->right=NULL;
    DeleteTree(p);
    }
    }

    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)