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

Answer 2

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;     }   } }