8
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ Could you please mention the desired output for your example? $\endgroup$
    – Syed
    Apr 16 at 5:03
  • $\begingroup$ 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]}]}], $\endgroup$
    – Henrik Schumacher
    Apr 16 at 16:58
  • $\begingroup$ @HenrikSchumacher sure i'll use that $\endgroup$
    – M.R.
    Apr 18 at 18:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jason B.
    Apr 18 at 19:03
  • $\begingroup$ @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! $\endgroup$
    – bmf
    Apr 21 at 20:11

4 Answers 4

Reset to default
4
$\begingroup$

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}

enter image description here

Improve this answer
$\endgroup$
3
$\begingroup$

The documented way using only Trees functionality is:

TreeLevel[tree, All -> "Data"]
Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – user5601
    May 12 at 21:51
  • $\begingroup$ @user5601 Length @ TreeLevel[RandomTree[2], All -> "Data"] gives 2 for me in 13.0.1, what version are you using? $\endgroup$
    – Ian Ford
    May 13 at 22:55
  • 1
    $\begingroup$ A faster approach is List @ TreeFold[{Sequence @@ #2 &, # &}, tree]. TreeLevel itself could be sped up. $\endgroup$
    – Ian Ford
    May 13 at 22:58
  • 1
    $\begingroup$ Thanks that does seem faster, but can you do BreadthFirst? $\endgroup$
    – user5601
    May 16 at 17:52
  • 1
    $\begingroup$ 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}*) $\endgroup$
    – M.R.
    May 16 at 19:44
1
$\begingroup$ 
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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – M.R.
    Apr 16 at 1:21
-1
$\begingroup$

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} *)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ that's was my starting point see above $\endgroup$
    – M.R.
    Apr 18 at 16:22
  • $\begingroup$ @M.R. - then you had the answer all along! $\endgroup$
    – Jason B.
    May 10 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.