A solution to the inability to set up a separate structure to keep track of the traversal is to use the pointer fields in the objects being traversed to store the information that would have gone into the stack. We of course have to restore this information when we're done.

Here's how this technique would work with a linked list. Our task is to go down to the end of the list, then to come back up, revisiting the nodes in reverse order. It's easy enough to go down the list with just an auxiliary pointer:

With just this one pointer, once we hit vertex 4 we have no way to go back up to 3 (remember that occasionally in graph traversal we have to backtrack). An idea: add one more auxiliary pointer, and reference the pointers as we go:

Notice how now once we hit vertex 4, it will be possible to traverse all the way back up to 1.

Figure out what the statements should be that complete the next step of the backward traversal, that is, the statements that take us from

to

Check your answer with a neighboring group.

Let's expand the idea of reversed linked list traversal without a stack to tree traversal without a stack.

We now present an algorithm due to Deutsch, Schorr, and Waite that traverses a binary tree without a stack, using only a constant amount of space plus a "tag" bit and a back-pointer bit in each node. Two pointers are maintained, one named current and the other prev. Going down the tree, current leads the way; prev points to the parent. Going back up the tree, prev leads the way. The myLeft and myRight pointers keep track of where we've been, and the back-pointer bit indicates which field in the node contains the back pointer. Here are the possibilities.

Notation

What happens when we traverse down the left one step:

What happens when we traverse down the right one step (if, say, the left is blocked):

Switching from a left branch to a right branch

Backing up one step when the back pointer is in the myLeft field

Backing up one step when the back pointer is in the myRight field

We've now seen this pointer-reversal idea used for singly linked lists and binary trees (and graphs with out-degree 2). It can be generalized to more than two outgoing pointers per object; each outgoing pointer is reversed to temporarily hold an incoming pointer.

Thus the garbage collection system is using the programmer's own data structures. Garbage collection must leave them in the same form as they started. The "going back up" process does this.

Cool, right?

In practice, most programs contain a small number of objects that live for a long time, and a large number of objects that come and go quickly. A technique called generational garbage collection handles this by segregating objects that have been around a long time into their own section of memory. These sections of older "generations" get traversed less frequently.

The various steps of garbage collection all basically take over the processing while they do their work. Some real-time applications, however, can't afford to be interrupted by a process as complicated as garbage collection. Modern operating systems allow concurrent garbage collection, where the garbage collector is allowed to run for a short while, then the application program (even though the garbage collection process hasn't finished!), switching back and forth between the two.