Re^3: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams?

jryan,
Again, I am at the conference so I don't have the time to give you a proper response. The second one, which is more memory efficient, only requires as many nodes on the stack as the max depth of the tree. It does this by creating an iterator (one item) for the stack instead of a list of nodes (many) to visit. You then work through that iterator before moving on. This is a poor explanation - I know, but I won't be available to explain in detail until Thursday.

Cheers - L~R

Comment on Re^3: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams?

Replies are listed 'Best First'.
Re^4: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams? by ikegami (Patriarch) on Jun 17, 2008 at 14:50 UTC
In case you're curious, only requires as many nodes on the stack as the max depth of the tree. So does mine below. It does this by creating an iterator (one item) for the stack instead of a list of nodes (many) to visit. Mine doesn't wrap the array index in an iterator. I started making a version that did, but it was complicating the ability to return the path that led to the node (like the OP's) instead of just the node (like yours).	[reply]

Replies are listed 'Best First'.

Re^4: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams?
by ikegami (Patriarch) on Jun 17, 2008 at 14:50 UTC

In case you're curious,

only requires as many nodes on the stack as the max depth of the tree.

So does mine below.

It does this by creating an iterator (one item) for the stack instead of a list of nodes (many) to visit.

Mine doesn't wrap the array index in an iterator. I started making a version that did, but it was complicating the ability to return the path that led to the node (like the OP's) instead of just the node (like yours).

[reply]