algorithm - Traversing a n-ary tree without using recurrsion

Question

How can I traverse an n-ary tree without using recursion?

Recursive way:

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

Answer 1

What you are doing is essentially a DFS of the tree. You can eliminate recursion by using a stack:

traverse(Node node) {
    if (node==NULL)
        return;

    stack<Node> stk;
    stk.push(node);

    while (!stk.empty()) {
        Node top = stk.pop();
        for (Node child in top.getChildren()) {
            stk.push(child);
        }
        process(top);
    }
}

If you want a BFS use a queue:

traverse(Node node) {
    if (node==NULL)
        return;

    queue<Node> que;
    que.addRear(node);

    while (!que.empty()) {
        Node front = que.deleteFront();
        for (Node child in front.getChildren()) {
            que.addRear(child);
        }
        process(front);
    }
}

In case you want some other way to traverse, you'll have to follow the same approach albeit with a different data structure to store the node. Maybe a priority queue (if you want to evaluate a function at each node and then process nodes based on that value).