Traversing Binary Trees Iteratively: Inorder Traversal

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

[Prev] [Up] [Next]

Inorder Traversal

Its recursive method can be written as:

void in(node *x)
{
  /* RP 0 */
  if(x->lc) in(x->lc);
  /* RP 1 */
  process(x);
  if(x->rc) in(x->rc);
  /* RP 2 */
}

Consider the iteration where current element is (x: 0). We cannot do process(x) without completing the traversal of the left child subtree. So we push (x→lc : 0) on the stack (if x→lc is not null) over the existing (x: 0) element, and update (x: 0) to (x: 1) to indicate that in(x) will later resume execution at resume-point 1. Next iteration and possibly its following ones will complete the traversal of the left-child subtree. If x→lc is null, the current element can eﬀectively be treated as (x: 1).

When an iteration will ﬁnd (x: 1) as the current (topmost) element, it will do process(x), pop this element, and push (x→rc : 0) if x→rc is not null. The current element could be popped because we now don’t need to remember anything for invocation of in(x), and so can get rid of it from the stack.

Thus, for this traversal, the stack will consist of two kinds of elements (x: 0) and (x: 1). The ﬁrst kind can only be found on the top of the stack.

We may keep the resume-point number within each element of the stack. But instead of that, we can derive its value for the current element. If the last iteration pushed an element on the stack, we derive the current element’s resume-point as 0. Otherwise, we default to the only remaining possibility of 1. Thus, each element in the stack can simply be a node pointer.

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

void in_i(node *root)
{
  node *stack[1000];
  int top;
  char pushed;

  stack[0] = root;
  top = 0;
  pushed = 1;

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

    if(pushed)
    {
      /* type (x: 0) */
      if(curr->lc)
      {
        stack[++top] = curr->lc;
        continue;
      }
    }

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

    if(curr->rc)
    {
      stack[++top] = curr->rc;
      pushed = 1;
    }
  }
}

[Prev] [Up] [Next]