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

With (1) an "up" pointer at each node and (2) a traversal counter at each node. You don't need a stack, since the tree itself already is (or contains) all the stack you need.

The combinator crunching program Combo uses totally non-recursive tree routines, along similar lines.

You just need to be aware (as stated in the "Combo" source code) that special measures will need to be taken if you're going to do this in a concurrent environment. Actually ... the source doesn't even use an "up" pointer, either. I just noticed. There's your challenge. Trying doing it without an "up" pointer.

If you get exhausted trying to solve the puzzle (and can't see an actual application of the solution, as seen in the link above) then a little more detailed description may be found here in this reply: Can I do inorder traversal of a binary tree without recursion and stack?. Here, I'll illustrate the traversal on the labeled binary tree given by the term a(b(c, d), e), which consists of a root tree with label a, that branches to a tree labeled b and leaf labeled e, with the sub-tree branching to leaves c and d.

The tree links, during the traversal, are (P,E,N), with E - the current location in the traversal - listed as label(head, tail, visits), and the NULL link listed as "·".

    P       E               N       action
    ·       a(b,e,0)        -       Spin
    -       a(e,·,1)        b       Down
    a       b(c,d,0)        -       Spin
    -       b(d,a,1)        c       Down
    b       c               -       Flip
    -       c               b       Down
    c       b(d,a,1)        -       Spin
    -       b(a,c,2)        d       Down
    b       d               -       Flip
    -       d               b       Down
    d       b(a,c,2)        -       Spin
    -       b(c,d,0)        a       Down
    b       a(e,·,1)        -       Spin
    -       a(·,b,2)        e       Down
    a       e               -       Flip
    -       e               a       Down
    e       a(·,b,2)        -       Spin
    -       a(b,e,0)        ·       Down
    a       ·               -       Done

So, for instance, if you're writing the labels in prefix order (abcde), you write the labels of the non-leaf nodes before bumping up the visits from 0 to 1. If you're writing in infix order (cbdae), you write them as you bump up the visits from 1 to 2. If you're writing them in postfix order (cdbea), you write them out as you cycle the visits from 2 back down to 0. A non-leaf node is off-limits to concurrent traversal, except when its visits is 0.

Answer 2

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).

Answer 3

You can do this without recursion and without a stack. But you need to add two extra pointers to the node:

1. The parent node. So you can come back to the parent if you are finished.

2. The current child node so you know which one to take next.

   • For each node, you handle all the kids.
   • If a kid is handled, you check if there is a next kid and handle that (updating the current).
   • If all kids are handled, go back to the parent.
   • If the node is NULL, quit.

With pseudocode this looks like:

traverse(Node node) {
  while (node) {
    if (node->current <= MAX_CHILD) {
      Node prev = node;
      if (node->child[node->current]) {
        node = node->child[node->current];
      }
      prev->current++;
    } else {
      // Do your thing with the node.
      node->current = 0; // Reset counter for next traversal.
      node = node->parent;
    }
  }
}

Answer 4

No language given, so in pseudo-pseudocode:

traverse(Node node)
{
  List<Node> nodes = [node];

  while (nodes.notEmpty) {
    Node n = nodes.shift();

    for (Node child in n.getChildren()) {
      nodes.add(child);
    }

    // do stuff with n, maybe
  }
}

Note that this is a breadth-first traversal as opposed to the depth-first traversal given in the question. You should be able to do a depth-first traversal by poping the last item off the nodes list instead of shifting the first one.