CareerCup

Quick (without thought!) recursive version

void Delete(Tree *root) {
    if (root == NULL) return;
    for (int i = 1; i <= root->numChildren; i++) {
        Delete(root->Child(i));
    }
    free(root);
}

You can understand the solution for a binary tree and then you can proceed for any n-ary tree basically the thing is all the child subtrees should be deleted before the node itself. So it follows kind of postorder traversal. You can watch a very helpful link to understand this concept at youtube.com/watch?v=qZbmY-2Y26Y

I would just say how is the tree implemented?
1. Using child-sibling concept?
2. Using only child concept & no sibling?

my_delete(root) //case 1
{
	if(root)
	{
		my_delete(root->child);
		my_delete(root->sibling);
		free(root);
	}
}

Assume N -ary tree.

my_delete(root) //case 2
{
	if(root)
	{
		for(i=0;i<N;i++)
			my_delete(root->child[i]);
		free(root);
	}
}

Below is the iterative implementation using a single stack of size of the tree height. Also including the driver program to test it (complete working version).

#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

struct Node {
	int data;
	vector<Node*> children;
};

Node *add_node(Node *root, int data)
{
	if (NULL == root)
		return NULL;

	Node *node = new Node;
	node->data = data;
	root->children.push_back(node);
	return node;
}

void delete_nodes_iterative(Node *root)
{
	stack<Node*> stnodes;
	Node *cur = root;
	stnodes.push(cur);

	while (true) {
		cur = stnodes.top();
		printf("size: %d; cur: %d\n", stnodes.size(), cur->data);

		if(cur->children.size() > 0) {
			stnodes.push(cur->children[0]);
			cur->children.erase(cur->children.begin());  // unlink from parent but do not delete the node itself
		}
		else { // leaf node
			stnodes.pop();
			printf("\tdel: %d\n", cur->data);
			delete cur;
		}

		if (stnodes.empty())
			break;            
	}
}

int main()
{
	Node *root = new Node;
	root->data = 1;

	Node *n2 = add_node(root, 2);
	Node *n3 = add_node(root, 3);
	Node *n4 = add_node(root, 4);
	Node *n5 = add_node(n2, 5);
	Node *n6 = add_node(n2, 6);
	Node *n7 = add_node(n2, 7);
	Node *n8 = add_node(n3, 8);
	Node *n9 = add_node(n3, 9);
	Node *n10 = add_node(n3, 10);
	Node *n11 = add_node(n4, 11);
	Node *n12 = add_node(n4, 12);
	Node *n13 = add_node(n4, 13);
	Node *n14 = add_node(n4, 14);
	Node *n15 = add_node(n5, 15);
	Node *n16 = add_node(n5, 16);
	Node *n17 = add_node(n5, 17);
	Node *n18 = add_node(n6, 18);
	Node *n19 = add_node(n11, 19);
	Node *n20 = add_node(n11, 20);
	Node *n21 = add_node(n16, 21);
	Node *n22 = add_node(n16, 22);

	delete_nodes_iterative(root);
}

Given the condition of the tree being not a binary tree, we cannot assume to be BT or BST and apply postorder.
I think the solution would be DFS traversal with deleting the leaf node.