English Idiom in Unix: Directory Recursively

[Raymond Wiker]

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

> ["Followup-To:" header set to comp.lang.python.]
> On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
>   <raw at RAWMBP-2.local> wrote:
> :  	I don't think anybody mentioned *binary* trees. The context was
> :  directory traversal, in which case you would have nodes with an
> :  arbitrary (almost) number of children.
>
> If we are being specific, then directory trees do have parent pointers.
> My point was really that «standard tree representations» is not a
> well-defined concept, and having parent pointers is as standard as
> not having them.

	I cannot see that going back to the original case (directory
traversal) is any more specific than talking about a completely
unrelated case (binary trees).

	Further, even though most(?) hierarchical file systems have parent
pointers, this is not necessary.

> :  	Except that the chain of parent pointers *would* constitue a
> :  stack. 
>
> In the sense that the tree itself is a stack, yes.  But if we
> consider the tree (or one of its branches) to be a stack, then
> the original claim becomes a tautology.

	No, the tree is not a stack, but the chain of parent pointers
from a particular node may be considered as a stack that records the
path taken to reach the current node.
 
> But you do have a point.  Keeping a stack of nodes on the path
> back to root is a great deal simpler and cheaper than a call
> stack, and not really a significant expense in context.

	For this particular operation, possibly. For other tree
operations, a single parent pointer may not be sufficient.