Visiting nodes in a tree bottom up

Question

I have a problem that can be reduced to this one:

Suppose I have an unbalanced (almost random) tree. The leaves of the tree have one property already set, and all vertex (including the leaves) have another property that I have to update upon visiting.

To update that property, I need to cast a function f[father_Vertex,{son_Vertex..}] in an ordered way, as shown below:

Example

(*build some tree*)
s = KaryTree[23, 3, DirectedEdges -> True];
leaves = Flatten@Position[VertexDegree[s], 1];
(*Draw it*)
HighlightGraph[#, leaves, VertexLabels -> "Name", ImagePadding -> 20] &@s
(*Assign a property to the leaves*)
leaves = Flatten@Position[VertexDegree[s], 1]
s1 = Fold[SetProperty[{#1, #2}, "leavesProp" -> RandomInteger[{1, 5}]] &, s, leaves];
(*Assign another property to all Vertex*)
s2 = Fold[SetProperty[{#1, #2}, "toUpdateProp" -> ""] &, s1, VertexList[s1]];

Now, to cast my function, I need to visit node sets updating the properties in a hierarchical order:

Which is the easiest way to accomplish this navigation scheme?

Edit

The visiting order at each tree level is interchangeable {s1, s2, s3, s4} and {s5, s6, s7}

Edit2

Trying to be more clear. This is the desired order of invocation. All calls to f within the same round could be done in any order. The red one could be done in the first or second round.

Answer 1

You can build the list of elements of the form {parent,childrenlist}, ordered by tree depth (largest first), as below.

Clear[distance, ordervertices, orderedvertices, families, children, 
  orderedparents, orderedvisits];

distance[s_, v_] := Length[FindShortestPath[s, 1, v]] - 1

ordervertices[s_] := 
 With[{verts = VertexList[s]}, 
  verts[[Reverse[Ordering[Map[distance[s, #] &, verts]]]]]]

ordervertices = ordervertices[s2]

(* Out[245]= {23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, \
8, 7, 6, 5, 4, 3, 2, 1} *)

families = 
 Map[{#[[1, 1]], #[[All, 2]]} &, 
  SplitBy[Sort[List @@@ EdgeList[s2]], First]]

(* Out[246]= {{1, {2, 3, 4}}, {2, {5, 6, 7}}, {3, {8, 9, 10}}, {4, {11, 
   12, 13}}, {5, {14, 15, 16}}, {6, {17, 18, 19}}, {7, {20, 21, 
   22}}, {8, {23}}} *)

Map[(children[#[[1]]] = #[[2]]) &, families];

orderedparents = 
 Select[ordervertices, MemberQ[families[[All, 1]], #] &]

(* Out[249]= {8, 7, 6, 5, 4, 3, 2, 1} *)

orderedvisits = Map[{#, children[#]} &, orderedparents]

(* Out[250]= {{8, {23}}, {7, {20, 21, 22}}, {6, {17, 18, 19}}, {5, {14, 
   15, 16}}, {4, {11, 12, 13}}, {3, {8, 9, 10}}, {2, {5, 6, 
   7}}, {1, {2, 3, 4}}} *)

Probably does not answer your question, but way too long for a comment. I'm sure the code could be improved also, though it should be fine for smallish graphs.