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? Commented May 20, 2012 at 9:51
• It is a given that all left branches are numbers (and even more specifically, integers). Thanks. Commented May 20, 2012 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!
– rm -rf
Commented May 18, 2012 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
– rm -rf
Commented May 18, 2012 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.
– rm -rf
Commented May 19, 2012 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. Commented May 26, 2012 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}}}}. Commented Aug 19, 2012 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
Commented May 26, 2012 at 14:39

Here is another way:

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

• Seems to break with trees with variable-depth branches: eg try B2 = {423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, {40, 41}}}}}; Commented Feb 26, 2018 at 18:14