Traversing Binary Trees Iteratively: Preorder Traversal

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Preorder Traversal

In the pre() method (page §), we can note that once we execute process(x) and have saved both x→lc and x→rc somewhere for performing the recursive calls, we no longer need to remember node x. We can beneﬁt from this fact in our iterative method. Consider the iteration where current element is (x: 0). It can be handled as:

process(x)
pop (x: 0)
if x→rc is not null, push (x→rc : 0)
if x→lc is not null, push (x→lc : 0).

We popped the element in Step 2 as it will no longer be needed.

Note that in this traversal’s case, the stack will consist of only one kind of elements, of the form (x: 0). So, we need not store the resume-point for each element as it is implied to be 0 always. Thus, each element in the stack can simply be a node pointer. As there are only one kind of elements on the stack, so the logic for handling the elements in an iteration becomes simpler.

In this and other iterative methods, the stack is a ﬁxed-size array, but other ways to store the stack can be used. Code for bound-checking the stack array has not been shown. The code portion of an iteration, where a speciﬁc type of stack element is handled is marked with a comment mentioning the element’s type, e.g. /* type (x: 0) */.

The iterative method pre_i() can be written as below:

void pre_i(node *root)
{
  node *stack[1000];
  int top;

  stack[0] = root;
  top = 0;

  while(top >= 0)
  {
    node *curr = stack[top];

    /* type (x: 0) */
    process(curr);
    top--;

    if(curr->rc) stack[++top] = curr->rc;

    if(curr->lc) stack[++top] = curr->lc;
  }
}

[Prev] [Up] [Next]