Why flatten a tree when you can just traverse it?
Michael Feathers wrote a blog post about avoiding explicitly traversing a tree recursively by taking advantage of its representation as nested arrays and using array operations to flatten.
I was unhappy about this solution because
- it creates a bunch of intermediate arrays
- it concatenates arrays repeatedly, which is expensive for a very large tree
- the recursive solution seems more simple, clear, and efficient
So I wrote up the recursive solution. Some features of the solution:
- it uses Ruby’s idiomatic
yieldconstruct - for convenience, it creates an
Enumerableso that you can do whatever you want while iterating through the tree
Here’s the code:
I prefer an iterative walk, which defends against stack depth constraints.
I wrote such an implementation in Java in an answer on StackOverflow—one of my favorite answers that still hangs with no votes.
I'll address the stack blowing issue in an update, but have one comment for now: would you like to modify your StackOverflow example for the case of a non-binary tree as in this example (array of children)?
It's possible; the main change would be to the
Breadcrumbclass'srightIsNextBoolean field. Instead of it just needing to know if the next step is to go right or up, it would need to store an index into the child node array. Obviously, then, when that index is equal to the length of the array, it's time to go up.I'll think about this for a couple of days to make sure it's likely to work out.