# How to get all nodes in Tree?

What is the most efficient way to get the nodes of a Tree?

tree = Tree[1, {Tree[    2, {Tree[5, {Tree[12, None], Tree[13, None]}], Tree[6, None]}],    Tree[3, {Tree[7, {Tree[14, None], Tree[15, None], Tree[16, None]}],      Tree[8, None], Tree[9, None]}],    Tree[4, {Tree[10, {Tree[17, None], Tree[18, None], Tree[19, None]}],      Tree[11, None]}]}];

Sort@Reap[TreeScan[Sow, tree]][[2, 1]] (* this seems wrong *)


Desired output: Range[19]

Follow-up: is there a way to get Annotate to work on Tree to store data in each node?

– Syed
Commented Apr 16, 2022 at 5:03
• Are you aware that node 4 appears twice? Maybe you meant to use Tree[1, {Tree[ 2, {Tree[5, {Tree[12, None], Tree[13, None]}], Tree[6, None]}], Tree[3, {Tree[7, {Tree[14, None], Tree[15, None], Tree[16, None]}], Tree[8, None], Tree[9, None]}], Tree[4, {Tree[10, {Tree[17, None], Tree[18, None], Tree[19, None]}], Tree[11, None]}]}], Commented Apr 16, 2022 at 16:58
• @HenrikSchumacher sure i'll use that
– M.R.
Commented Apr 18, 2022 at 18:30
• I don't know anything about the Tree data structure or if it's documented to work with VertexList, but it seems to. ContainsExactly[VertexList[tree][[All, 1]], Range[19]] returns True. Commented Apr 18, 2022 at 19:03
• @M.R after you edited your question, the following: Sort@Reap[TreeScan[Sow, tree]][[2, 1]] == Range@19 yields True. Can I ask for two things: one can you verify that, i.e that I did not make any mistakes? Two, do you still want a solution different than Sort@Reap[TreeScan[Sow, tree]][[2, 1]]? Could you explain why? Many thanks!
– bmf
Commented Apr 21, 2022 at 20:11

Looks like TreeGraph+VertexList+SortBy is the most efficient for Breadth First Search:

tree = RandomTree[5000];
RepeatedTiming[n1 = Reap[TreeScan[Sow, tree, TreeTraversalOrder->"BreadthFirst"]][[2, 1]];]
RepeatedTiming[n2 = SortBy[VertexList[TreeGraph[tree]],#[[2]]&][[All,1]];]
RepeatedTiming[n3 = TreeLevel[tree, All -> "Data", TreeTraversalOrder->"BreadthFirst"];]
RepeatedTiming[n4 = List @ TreeFold[{Sequence @@ #2 &, # &}, tree];] (* wrong *)
n1==n2==n3
Take[#,3]&/@{n1,n2,n3,n4}


The documented way using only Trees functionality is:

TreeLevel[tree, All -> "Data"]

• This is the simplest, but doesn't seem to be the fastest. Also is the root missing? Length@TreeLevel[RandomTree[2], All -> "Data"] is 1 but should be 2. Commented May 12, 2022 at 21:51
• A faster approach is List @ TreeFold[{Sequence @@ #2 &, # &}, tree]. TreeLevel itself could be sped up. Commented May 13, 2022 at 22:58
• Thanks that does seem faster, but can you do BreadthFirst? Commented May 16, 2022 at 17:52
• That TreeFold doesn't work at all for me... tree=Tree[1, {Tree[2, None], Tree[3, {Tree[4, None], Tree[5, None], Tree[6, None]}], Tree[7, None]}];List @ TreeFold[{Sequence @@ #2 &, #&}, tree] (*{2,4,5,6,7}*)
– M.R.
Commented May 16, 2022 at 19:44
• @M.R. Sorry, my previous comment incorrectly gives just the data of the leaves. lericr's answer Flatten@TreeFold[List,tree] gives the data of all nodes. Commented May 17, 2022 at 18:51
TreeLeaves[tree]


Or maybe

TreeCases[tree, _]


Or maybe

Flatten @ TreeFold[List, tree]


You might want to peruse http://reference.wolfram.com/language/guide/ComputationOnTrees.html

• Three points: TreeLeaves doesn't return the root nor does it strip the nodes out; TreeCases returns subtrees - not what I want; and TreeFold maintains the structure which is inefficient for large trees.
– M.R.
Commented Apr 16, 2022 at 1:21

You could try to traverse the tree and return every leaf, collecting them using Reap. E.g.:

Reap[
TreeScan[Sow, tree]
][[2,1]]

(* {11, 12, 4, 5, 2, 13, 14, 15, 6, 7, 8, 3, 16, 17, 18, 9, 10, 4, 1} *)

• that's was my starting point see above
– M.R.
Commented Apr 18, 2022 at 16:22
• @M.R. - then you had the answer all along! Commented May 10, 2022 at 20:34