English Idiom in Unix: Directory Recursively

[Pascal J. Bourguignon]

tar at sevak.isi.edu (Thomas A. Russ) writes:

> 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.

No, you don't need backpointers; some cases have been mentionned in the
other answer, but in general:

    (defun parent (tree node)
       (if (member node (children tree))
          tree
          (some (lambda (child) (parent child node)) (children tree))))

Yes, the question wasn't about time complexity.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.