CSE 130 Spring 2011 - Style Exercise 2

Name/SID: ______________________________/____________________

Consider the following Ocaml datatype representing red-blue trees.

type ('a, 'b) rbtree = Red  of 'a 
                     | Blue of 'b 
                     | Node of ('a, 'b) rbt * ('a, 'b) rbt

Problem 1: Write an OCaml function

val redSum : (int, 'a) rbtree -> int 

that returns the sum of the integers occurring as Red leaves of the red-blue tree. Thus,

• redSum (Node (Red 10, Node(Blue 5, Red 20))) should yield 30
• redsum (Node (Node (Red 100, Red 2), Node (Red 5, Blue 20))) should yield 107

Problem 2: Write an Ocaml function

val diff : (int, int) rbtree -> int 

such that diff t returns the number of red leaves minus the number of blue leaves. Thus,

• diff (Node (Red 10,Node(Blue 5, Red 20))) should yield 1
• diff (Node (Node (Blue 100, Blue 2), Node (Blue 5, Red 20))) should yield -2

Problem 3: Write an Ocaml function

val flipColor : ('a, 'b) rbtree -> ('b, 'a) rbtree

such that flipColor t returns a tree that looks like t with the leaf colors flipped. Thus,

• flipColor (Node (Red 5.0, Blue 2)) should yield Node (Blue 5.0, Red 2)
• diff (Node (Node (Blue "100", Blue "2"), Node (Blue "5", Red 20))) should yield (Node (Node (Red "100", Red "2"), Node (Red "5", Blue 20)))