Home

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



[Prev]   [Up]   

Postorder Traversal

Its recursive method can be written as:

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

Consider the iteration where current element is (x: 0). This will be handled as:

  1. if xrc is not null, push (xrc : 0)
  2. if xlc is not null, push (xlc : 0)
  3. update (x: 0) to (x: 2) leaving it where it was on the stack; it is now below the elements pushed by above steps.

If both child pointers are null, the current element can effectively be treated as (x: 2).

By pushing both the lc and rc pointers together, we have removed the need of keeping the post(x) invocation at resume-point 1 while the post(xlc) completes its execution. We made sure that both recursive invocations are taken care of by pushing their elements and so could directly shift (x: 0) to (x: 2). Again, similar to earlier traversals, this optimization helped in reducing the kinds of elements on the stack to two: (x: 0) and (x: 2). So, the logic for handling the elements in an iteration becomes simpler.

When an iteration finds (x: 2) as the current element, it can simply do process(x), and then pop this element.

We may keep the resume-point number within each element of the stack, but again we can try deriving it like earlier traversals. Note that elements of the form (x: 0) and (x: 2) can be anywhere on the stack in this case. When an iteration has current element (x: 2) and pops it, the next iteration’s element need not be for the parent of x; it can be for the sibling node of x (since left/right child pointers are pushed together). To derive the resume-point of current element, we can check if the last iteration popped a child (left or right) of the current node. If so, the resume-point is 2. Otherwise, we default to the only remaining possibility of 0. Thus, like earlier traversals, each element in the stack can simply be a node pointer.

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

void post_i(node *root)  
{  
  node *stack[1000];  
  int top;  
  node *popped;  
 
  stack[0] = root;  
  top = 0;  
  popped = NULL;  
 
#define POPPED_A_CHILD() \  
  (popped && (popped == curr->lc || popped == curr->rc))  
 
  while(top >= 0)  
  {  
    node *curr = stack[top];  
 
    if(!POPPED_A_CHILD())  
    {  
      /* type (x: 0) */  
      if(curr->rc || curr->lc)  
      {  
        if(curr->rc) stack[++top] = curr->rc;  
 
        if(curr->lc) stack[++top] = curr->lc;  
 
        popped = NULL;  
        continue;  
      }  
    }  
 
    /* type (x: 2) */  
    process(curr);  
    top--;  
    popped = curr;  
  }  
}

[Prev]   [Up]