# Determining all possible traversals of a tree

I have a list:

B={423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}};

This list can be visualized as a tree using TreeForm[B]:

and I would like to find all possible traversals of this tree:

{{423,53,39},{423,53,65},{423,53,423},{423,66,67},{423,66,81},
{423,66,423},{423,424,25},{423,424,40},{423,424,423}}

It seems that Subset might be usable, but when I tried Subset[B,{3}], it gave me the null set. Another possible problem with Subset is that it perhaps does not respect the leveling of the tree. I looked at the Combinatorica package, but I don't see a way to traverse the tree -- in the direction from top to bottom -- in all possible ways.

-
Are you looking for solutions for this specific tree B or for general trees? B has the property that all left branches are numbers. Is that a given? – Sjoerd C. de Vries May 20 '12 at 9:51
It is a given that all left branches are numbers (and even more specifically, integers). Thanks. – Andrew May 20 '12 at 15:40

Here is one way:

ClearAll[f];
f[tree_List] := Flatten[f[{}, tree], 1];
f[accum_List, {x_, y_List}] := f[{accum, x}, #] & /@ y;
f[x_, y_] := Flatten[{x, y}];

The usage is

f[B]
-
I don't think I can beat this! – R. M. May 18 '12 at 21:58
Uhh whoa! That's my line, when you say something like my comment! Not the other way round :) I've just thrown in the towel at Step 0 :P – R. M. May 18 '12 at 22:02
@Andrew You can replace the first definition for f with f[tree_List] := Flatten[f[{}, tree], {1}];. The additional change as a result of this is that the final output will have all the paths from each "major branch" (or what ever the right term is) grouped together. I actually like it this way and you can flatten this out appropriately in a post-processing step. Run the new definition on B to see what I mean. – R. M. May 19 '12 at 1:22
@acl Thanks for the upvote and kind words. The thing is, I was prepared for this question, having done similar things in the past. What may look clever from the outset is often just a result of some practice and preparation, you just have to think in a certain direction. Once you apply some new (to you) technique a few times, it grows on you and leads your thoughts, and then it is not particularly hard. I think this applies to anything (I do know from experience that it also applies to physics and math). You just need to have a free mind and time to experiment on your own, that's all. – Leonid Shifrin May 26 '12 at 16:19
@Andrew We can also replace the first definition of f by f[tree_List] := List@@@Flatten@Apply[lst, f[{}, tree], {-2}];. Now f will work for {423,{53,66,424}} as well as {423, {{53, {39, {66, {67, 81, 423}}, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}}. – Michael Wijaya Aug 19 '12 at 2:14

Here is a transformation that will work as well:

Flatten[B //. {
{x__?NumericQ, {y__?NumericQ}} :> ({x, #} & /@ {y}),
{x__?NumericQ, {y__List}} :> (Join[{x}, #] & /@ {y})
}, 1]

yields

{{423, 53, 39}, {423, 53, 65}, {423, 53, 423}, {423, 66, 67}, {423,
66, 81}, {423, 66, 423}, {423, 424, 25}, {423, 424, 40}, {423, 424,
423}}
-
nice, +1. however this doesn't seem to work generically ; try with {423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, {4, 3, 4, 2}, 423}}}} – acl May 26 '12 at 14:39

Here is another way:

(Thread@{First@B, #[[1]], #[[2]]} & /@ Flatten[Rest@B, 1])~Flatten~1
-