Traverse tree without recursion and stack in C

Question

How to traverse each node of a tree efficiently without recursion in C (no C++)?

Suppose I have the following node structure of that tree:

struct Node
{
    struct Node* next;   /* sibling node linked list */
    struct Node* parent; /* parent of current node   */
    struct Node* child;  /* first child node         */
}

• It's not homework.
• I prefer depth first.
• I prefer no additional data struct needed (such as stack).
• I prefer the most efficient way in term of speed (not space).
• You can change or add the member of Node struct to store additional information.

Answer 1

Generally you'll make use of a your own stack data structure which stores a list of nodes (or queue if you want a level order traversal).

You start by pushing any given starting node onto the stack. Then you enter your main loop which continues until the stack is empty. After you pop each node from the stack you push on its next and child nodes if not empty.

Answer 2

You'd have to store it in an iterable list. a basic list with indexes will work. Then you just go from 0 to end looking at the data.

If you want to avoid recursion you need to hold onto a reference of each object within the tree.

Answer 3

If you don't want to have to store anything, and are OK with a depth-first search:

process = TRUE;
while(pNode != null) {
    if(process) {
        //stuff
    }
    if(pNode->child != null && process) {
         pNode = pNode->child;
         process = true;
    } else if(pNode->next != null) {
         pNode = pNode->next;
         process = true;
    } else {
         pNode = pNode->parent;
         process = false;
    }
}

Will traverse the tree; process is to keep it from re-hitting parent nodes when it travels back up.

Answer 4

You can use the Pointer Reversal method. The downside is that you need to save some information inside the node, so it can't be used on a const data structure.

Answer 5

This looks like an exercise I did in Engineering school 25 years ago. I think this is called the tree-envelope algorithm, since it plots the envelope of the tree.

I can't believe it is that simple. I must have made an oblivious mistake somewhere. Any mistake regardless, I believe the enveloping strategy is correct. If code is erroneous, just treat it as pseudo-code.

while current node exists{
  go down all the way until a leaf is reached;
  set current node = leaf node;
  visit the node (do whatever needs to be done with the node);

  get the next sibling to the current node;
  if no node next to the current{
    ascend the parentage trail until a higher parent has a next sibling;
  }
  set current node = found sibling node;
}

The code:

void traverse(Node* node){

  while(node!=null){
    while (node->child!=null){
      node = node->child;
    }

    visit(node);

    node = getNextParent(Node* node);
  }
}

/* ascend until reaches a non-null uncle or 
 * grand-uncle or ... grand-grand...uncle
 */
Node* getNextParent(Node* node){

  /* See if a next node exists
   * Otherwise, find a parentage node
   * that has a next node
   */
  while(node->next==null){
    node = node->parent;
    /* parent node is null means
     * tree traversal is completed
     */
    if (node==null)
      break;
  }

  node = node->next;

  return node;
}