Algorithms Design | Index

Iterative left-root-right traversal

[Statement of exercise]  Iterative code for left-root-right traversal (of a binary tree) that manipulates the stack of nodes directly (rather than using the functions push and pop):

// Receives the root r of a binary tree and 
// prints the contents of its nodes in
// left-root-right order.

void i_leftrootright (tree r) {
    node *x, *stack[101];
    int t = 0;
    stack[t++] = r;
    while (1) {
       // stack[0..t-1] is a stack of nodes
       x = stack[t-1];
       if (x != NULL) 
          stack[t++] = x->lft;
       else {
          if (t == 0) break;
          x = stack[--t];
          printf ("%d\n", x->contents);
          stack[t++] = x->rght;
       }
    }
}

This version assumes that the height of the tree is at most 100, but it is easy to remove this restriction by allocating a stack of appropriate size.

Note the similarity between this code and the code of the function that enumerates subsequences of 1..n in lexicographic order.