Delete a Tree

To delete a tree we must traverse all the nodes of the tree and delete them one by one.

So which traversal we should use – Inorder or Preorder or Postorder. Answer is simple – Postorder, because before deleting the parent node we should delete its children nodes first

void deleteTree(Node node) {
		
		if (node == NULL)
			return;

		/* first delete both subtrees */
		deleteTree(node.left);
		deleteTree(node.right);

		/* then delete the node */
		syso("\n Deleting node: ", node.data);
		node = null;
	}

Tip -

Post-order traversal is useful in some types of tree operations:

a) Tree deletion. To free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node can only be deleted when both of its left and right subtrees are deleted.
b) Evaluating post-fix notation.


References -

http://geeksforgeeks.org/archives/654