CareerCup

you can do smth like this:
that is first reverse all children subtrees recursively, then
change the current node

add_leaf_to_list(node *t) {
// make a linked list out of nodes 't'
}

reverse_tree(node *t) {

    if(t == 0)
        return;

    for(i = 0; i < t->nchildren; i++) {
        reverse_tree(t->child[i]);
        t->child[i]->child[0] = t;
        t->child[i]->nchildren = 1;
    }
    if(t->nchildren == 0) 
        add_leaf_to_list(t);
}
reverseTreeandReturnListwithLeafNodes(node *root) {

reverse_tree(root);
}

I solved it using a recursive approach. Will post the solution later.

Thanks!

c++ code:
-------------

class NODE{
public:
    string Label
    vector<NODE*> children;
};

vector<Node*> 
reverseTreeandReturnListwithLeafNodes(NODE* n)
{
    vector<Node*> roots;
    reverseTree(roots, n);
    return roots;
}
NODE*
reverseTree(vector<Node*>& roots, NODE* n)
{
    vector<NODE*>& chldrn = n->children;
    if (chldrn.empty())  {
        roots->push_back(n);
        return n;
    }
    vector<NODE*> children = chldrn;
    chldrn.clear();
    vector<NODE*>::iterator iter = children.begin();
    for (; iter != children.end(); ++iter) {
        NODE* child = *iter;
        NODE* p = reverseTree(child);
        p->children.push_back(child);
    }

    return n;

}

sorry I made a small mistake. it should be NODE* p = reverseTree(n); instead of NODE* p = reverseTree(child); reposting the correct code:

class NODE{
public:
    NODE(string d) : data(d) {}
    string data;
    vector<NODE*> children;
};
vector<NODE*>
reverseTreeandReturnListwithLeafNodes(NODE* n)
{
    vector<NODE*> roots;
    reverseTree(roots, n);
    return roots;
}
NODE*
reverseTree(vector<NODE*>& roots, NODE* n)
{
    vector<NODE*>& chldrn = n->children;
    if (chldrn.empty())  {
        roots.push_back(n);
        return n;
    }
    vector<NODE*> children = chldrn;
    chldrn.clear();
    vector<NODE*>::iterator iter = children.begin();
    for (; iter != children.end(); ++iter) {
        NODE* child = *iter;
        NODE* p = reverseTree(roots, child);
        p->children.push_back(n);
    }
    return n;

}

What does reverse an n-ary tree mean?

i think "p->children.push_back(n);" should be
p->children.push_back(p);

Will this work. In order preorder traversal o / p to list then reverse list

I think this can be solved using BFS.