+ HERE IS A DIRECT OCAML SOLUTION:
+
+ let rec tree_red_ancestors_from (cur : int) (t : 'a tree) : int tree =
+ match t with
+ | Leaf a -> Leaf cur
+ | Branch(l, col, r) ->
+ let cur' = if col = Red then cur + 1 else cur in
+ let l' = tree_red_ancestors_from cur' l in
+ let r' = tree_red_ancestors_from cur' r in
+ Branch(l',col,r')
+
+ (* here is the function we were asked for *)
+ let tree_red_ancestors t = tree_red_ancestors_from 0 t
+
+
+ HERE IS HOW TO DO IT USING `tree_walker`:
+
+ let tree_red_ancestors t =
+ let leaf_handler a = fun cur -> Leaf cur in
+ let joiner lh col rh = fun cur ->
+ let cur' = if col = Red then cur + 1 else cur in
+ Branch(lh cur', col, rh cur') in
+ tree_walker leaf_handler joiner t 0
+
+
+9. (More challenging.) Assume you have a `color_tree` whose leaves are labeled with `int`s (which may be negative). For this problem, assume also that no color labels multiple `Branch`s (non-leaf nodes). Write a recursive function that reports which color has the greatest "score" when you sum up all the values of its descendant leaves. Since some leaves may have negative values, the answer won't always be the color at the tree root. In the case of ties, you can return whichever of the highest scoring colors you like.
+
+ HERE IS A DIRECT OCAML SOLUTION:
+
+ type maybe_leader = (color * int) option
+
+ let rec tree_best_sofar (t : 'a color_tree) (lead : maybe_leader) : maybe_leader * int =
+ match t with
+ | Leaf a -> (lead, a)
+ | Branch(l, col, r) ->
+ let (lead',left_score) = tree_best_sofar l lead in
+ let (lead'',right_score) = tree_best_sofar r lead' in
+ let my_score = left_score + right_score in
+ (match lead'' with
+ | None -> Some(col,my_score), my_score
+ | Some(_, lead_score) -> (if my_score > lead_score then Some(col,my_score) else lead''), my_score)
+
+ (* Note that the invocations of that function have to return who-is-the-current-leader?
+ plus their OWN score, even if they are not the current leader. Their parents need the
+ second value to calculate whether they should become the current leader. *)
+
+ (* here is the function we were asked for *)
+ let tree_best t =
+ match tree_best_sofar t None with
+ | Some(leader,leader_score), _ -> leader
+ | None, _ -> failwith "no colors"
+
+
+ HERE IS HOW TO DO IT USING `tree_walker`:
+
+ let tree_best_sofar t =
+ let leaf_handler a = fun leader -> leader, a in
+ let joiner lh col rh = fun leader ->
+ let (leader',left_score) = lh leader in
+ let (leader'',right_score) = rh leader' in
+ let my_score = left_score + right_score in
+ (match leader'' with
+ | None -> Some(col,my_score), my_score
+ | Some(_,leader_score) -> (if my_score > leader_score then Some(col,my_score) else leader''), my_score) in
+ tree_walker leaf_handler joiner t
+
+ Then `tree_best` could be defined as in the direct answer.