# Interview Questions

# deleting a tree

- July 30, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

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)

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);

}

}

}