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?

$\endgroup$
5
  • 5
    $\begingroup$ Could you please mention the desired output for your example? $\endgroup$
    – Syed
    Commented Apr 16, 2022 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$ Commented Apr 16, 2022 at 16:58
  • $\begingroup$ @HenrikSchumacher sure i'll use that $\endgroup$
    – M.R.
    Commented Apr 18, 2022 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.
    Commented Apr 18, 2022 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
    Commented Apr 21, 2022 at 20:11

4 Answers 4

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

$\endgroup$
3
$\begingroup$

The documented way using only Trees functionality is:

TreeLevel[tree, All -> "Data"]
$\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
    Commented May 12, 2022 at 21:51
  • 1
    $\begingroup$ A faster approach is List @ TreeFold[{Sequence @@ #2 &, # &}, tree]. TreeLevel itself could be sped up. $\endgroup$
    – Ian Ford
    Commented May 13, 2022 at 22:58
  • 1
    $\begingroup$ Thanks that does seem faster, but can you do BreadthFirst? $\endgroup$
    – user5601
    Commented May 16, 2022 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.
    Commented May 16, 2022 at 19:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ian Ford
    Commented May 17, 2022 at 18:51
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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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