Traversing Binary Trees Iteratively: Resume-Points

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

[Prev] [Up] [Next]

Resume-Points

We will ﬁrst deﬁne Resume Points with the help of the below method as an example. This is the recursive method for Preorder traversal:

void pre(node *x)
{
  /* RP 0 */
  process(x);               /* step A */
  if(x->lc) pre(x->lc);     /* step B */
  /* RP 1 */
  if(x->rc) pre(x->rc);     /* step C */
  /* RP 2 */
}

Observe that the execution of pre(x) becomes active multiple times. It starts at step A. The recursive call at step B suspends its execution. Upon return of this recursive call, it becomes active again at location marked with “RP 1”. Similarly, after recursive call of step C returns, it becomes active again at location “RP 2”. We will refer to such instruction locations just after return from a recursive call as “Resume Point”, abbreviated as “RP”. In above method, there are two resume-points, marked “RP 1” and “RP 2”. The very ﬁrst instruction is not a resuming location, but still we will refer it as a special resume-point 0, and mark it “RP 0”. So, the execution of pre(x) becomes active at three diﬀerent times at resume-points 0, 1 and 2 respectively. Note, if the lc∕rc pointers are null, the execution simply continues without making the recursive call.

[Prev] [Up] [Next]