English Idiom in Unix: Directory Recursively

[Thomas A. Russ]

Hans Georg Schaathun <hg at schaathun.net> writes:

> ["Followup-To:" header set to comp.lang.python.]
> On 17 May 2011 23:42:20 -0700, Thomas A. Russ
>   <tar at sevak.isi.edu> wrote:
> :  Tree walks are the canonical example of what can't be done in an
> :  iterative fashion without the addition of an explicitly managed stack
> 
> Of course you can do it.  It isn't nice, but it is possible.
> I assume that you refer to depth first walks, as breadth first
> is more easily described by iteration on a queue in the first place.
> 
> Depth first can be achieved by looping over the nodes, with a
> state keeping references to the current and the previous node
> considered.

Well, unless you have a tree with backpointers, you have to keep the
entire parent chain of nodes visited.  Otherwise, you won't be able to
find the parent node when you need to backtrack.  A standard tree
representation has only directional links.

Consider:

A--+---B----+---D
   |        |
   |        +---E
   |        |
   |        +---F
   | 
   +---C

If all you keep is the current and previous node, then the only thing
you have reference do when doing the depth-first traverse is:
  1.  Current = A,  Previous = null
  2.  Current = B.  Previous = A
  3.  Current = D   Previous = B
  4.  Current = E   Previous = D
  5.  now what?  You can't get from E or D back to B.

> By comparing the previous node (pointer or ID) to the
> current node's parent and children one will know wherefrom the
> current node was entered, and can choose the next child in the
> list as the next node, or the parent if all children have been
> visited.  A visit action may be added in any or all times the
> node is visited.
> 
> This node requires no stack.  The only state space is constant,
> regardless of the size of the tree, requiring just the two pointers
> to previous and current.

This will only work if there is a backpointer to the parent.

So you have to add one extra pointer for each node back to its parent.
This extra pointer will be the size of the graph, rather than (on
average) log of the size of the graph stack frames.


-- 
Thomas A. Russ,  USC/Information Sciences Institute