# Depth first scan of a tree backwards

How can I traverse this tree, to get a sequence of vertices {8,4,2,9,5,1,6,3,7}? I've failed to produce it with DepthFirstScan, does this particular order even has a name?

TreeGraph[{1->2,1->3,2->4,2->5,3->6,3->7,4->8,5->9}, VertexLabels -> "Name"]


• Which algorithm did you use to produce this order or the vertices?
– A.G.
Sep 11, 2017 at 18:21
• You can get pretty close using DepthFirstScan and the "PostvisitVertex" event - are you sure that's not what you want? Your order seems a bit strange, given that e.g. 2 is visited between visiting the two subbranches Sep 11, 2017 at 18:58
• @A.G. I don't know what's the algorithm is called, but it outputs the vertices while backtracking backwards from DFS. Sep 11, 2017 at 20:40
• @swish As I understand a vertex is listed when the DFS has exhausted its adjacency list. If that is correct, node "1" should be last in the list. Is that correct?
– A.G.
Sep 11, 2017 at 22:16
• i am sure this is not what you want, but it does give {8,4,2,9,5,1,6,3,7}: rubeGoldbergSort[g_] := SortBy[VertexList[g], {PropertyValue[{g, #}, VertexCoordinates] &}]; rubeGoldbergSort@ TreeGraph[{1 -> 2, 1 -> 3, 2 -> 4, 2 -> 5, 3 -> 6, 3 -> 7, 4 -> 8, 5 -> 9}, VertexLabels -> "Name"]:)
– kglr
Sep 12, 2017 at 8:33

Based on swish's comment ("Suprisingly it also gives the right answer for a bigger tree graph I have, so it probably is not a coincidence and this sort function is indeed traverses the tree the way I want it to"), perhaps:

coordinateSort[g_] := SortBy[VertexList[g], PropertyValue[{g, #}, VertexCoordinates]&];

coordinateSort@TreeGraph[{1 -> 2, 1 -> 3, 2 -> 4, 2 -> 5, 3 -> 6, 3 -> 7, 4 -> 8, 5 -> 9}]


{8, 4, 2, 9, 5, 1, 6, 3, 7}

As noted in the comments, the following gets you close:

g = TreeGraph[{1->2,1->3,2->4,2->5,3->6,3->7,4->8,5->9}, VertexLabels -> "Name"]

Reap[DepthFirstScan[g, 1, {"PostvisitVertex" -> Sow}]][[2, 1]]
(* {8, 4, 9, 5, 2, 6, 7, 3, 1} *)


The difference between this and your order is that a vertex is only visited after all subbranches have been visited. (whereas your order lists them after the first subbranch, which seems a bit arbitrary)