*856*

Question:Given the root pointer to a binary tree, delete the binary tree

To delete a tree we must traverse all the nodes of the tree and delete them one by one. So which traversal should we use ? Inorder, Pre-order, Post-order or Level Order Traversal ?

Before deleting he parent node, we should delete its child node first. We can therefore use post order traversal as it does the work without storing anything. We can delete three with other traversals also but the space complexity will increase.

For the above given tree, the **tree will be deleted in the order :- 7, 9, 5, 4, 2, 3, 1**

#include<stdio.h> #include<malloc.h> struct binaryTreeNode{ int data; struct binaryTreeNode * left; struct binaryTreeNode * right; }; struct binaryTreeNode * deleteBinaryTree(struct binaryTreeNode * root) { if(root == NULL) return NULL; // Delete the sub-trees first root -> left = deleteBinaryTree(root -> left); root -> right = deleteBinaryTree(root -> right); // Delete the current node only after deleting sub-trees free(root); return NULL; }

*Time Complexity:-* O(n)

*Space Complexity:-* O(n)

**Ideone link for running program:-** http://ideone.com/pxE5EA