[This page is auto-generated; please prefer to read the article’s PDF Form.]
Its recursive method can be written as:
Consider the iteration where current element is (x: 0). This will be handled as:
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(x→lc) 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:
Copyright © 2020 Nitin Verma. All rights reserved.