+ 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 -> (None, 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.
+