Write an algorithm to delete a complete binary tree

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

Input: Sample Tree (Pointer to node 1 is given).

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