datatype 'a b_tree = Empty | Node of 'a b_tree * 'a * 'a b_tree;

fun height Empty = 0		(* height of b_tree *)
| height (Node (lft, _, rht)) = 1 + Int.max (height lft, height rht);

fun size Empty = 0		(* size of b_tree = # nodes *)
| size (Node (lft, _, rht)) = 1 + size lft + size rht;

	(* given boolean comparison function 'comp' of labels 'lab', and a b_tree
	(which is assumed realizes the order of 'comp'), inserts a new node on 
	the b_tree with 'lab' in its correct place in the order:
	helper function for 'create_tree' *)

fun insert_node (lab:'a, comp:'a*'a->bool, Empty) = Node (Empty, lab, Empty)
| insert_node (lab, comp, Node (lft, lab1, rht)) =
	if comp (lab, lab1) then Node (insert_node (lab, comp, lft), lab1, rht)
	else Node (lft, lab1, insert_node (lab, comp, rht));

	(* given list of labels and boolean comparison function 'comp'
	on labels, creates a b_tree realizing 'comp' *)

fun create_tree (nil, comp) = Empty
| create_tree (h::q, comp) = insert_node (h, comp, create_tree (q, comp));

val nums = [2, ~4, 0, ~1, 6];

fun lt (n1:int, n2:int) = n1 < n2;

val words = [
("gnu","a silly animal"),
("new","not old"),
("New","West Virginia river"),
("knew","used to know"),
("nu","Greek letter"),
("nuu","a nonsense word"),
("gnew","past tense of gnaw"),
("noo","sound of cow with nose cold")];

fun key (word:string, def:string ) = word;

fun compwords (word1:string*string, word2:string*string) = key(word1) < key(word2);

datatype 'a search_result = Stringans of string | Ans of 'a;

val europe =
  [("Andorra",450.0,65780.0,760000000.0),
   ("Austria",83850.0,7986664.0,139300000000.0),
   ("Belgium",30510.0,10081880.0,181500000000.0),
   ("Denmark",43070.0,5199437.0,103000000000.0),
   ("Estonia",45100.0,1625399.0,10400000000.0),
   ("Finland",337030.0,5085206.0,81800000000.0),
   ("France",547030.0,58109160.0,1080100000000.0),
   ("Germany",356910.0,81337541.0,1452200000000.0),
   ("Greece",131940.0,10647511.0,93700000000.0),
   ("Ireland",70280.0,3550448.0,49800000000.0),
   ("Italy",301230.0,58261971.0,998900000000.0),
   ("Latvia",64100.0,2762899.0,12300000000.0),
   ("Lichtenstein",160.0,30654.0,630000000.0),
   ("Lithuania",65200.0,3876396.0,13500000000.0),
   ("Luxembourg",2586.0,404660.0,9200000000.0),
   ("Malta",320.0,369609.0,3900000000.0),
   ("Monaco",1.0,31515.0,558000000.0),
   ("Netherlands",37330.0,15452903.0,275800000000.0),
   ("Norway",324220.0,4330951.0,95700000000.0),
   ("Portugal",92080.0,10562388.0,107300000000.0),
   ("San Marino",60.0,24313.0,380000000.0),
   ("Spain",504750.0,39404348.0,515800000000.0),
   ("Sweden",449964.0,8821759.0,163100000000.0),
   ("Switzerland",41290.0,7084984.0,148400000000.0),
   ("United Kingdom",244820.0,58295119.0,1045200000000.0)
];
fun name(x:string,_,_,_) = x;	(* name *)
fun area(_,x:real,_,_) = x;	(* area *)
fun pop (_,_,x:real,_) = x;	(* population *)
fun gdp (_,_,_,x:real) = x;	(* gross national product *)

(* The following function is a bonus.  It prints a tree in somewhat
recognizable tree fashion.  The main function is print_tree, which calls
print_treehelp for the recursive step.  The arguments are a tree, and
a function print_fun which is a string-valued function of the label.  The
tree is printed from left to right, and the connecting lines are not printed,
but one should be able to figure out how it all works (and be able to 
draw in the lines) from the code and from an example.  For example, after 
creating a tree t from the list nums, try
print_tree (t, Int.toString),
and compare it with the answer to part 2 of the project.  (Note: "\n" is a 
carriage return, and "\t" is a tab.)   *)

fun print_treehelp (Empty:'a b_tree, print_fun:'a -> string, indent:string) = print "\n"
| print_treehelp (Node (lft, lab, rht), print_fun, indent) = 
		(print_treehelp (lft, print_fun, indent^"\t"); 
		print (indent^(print_fun lab)^"\n"); 
		print_treehelp (rht, print_fun, indent^"\t"));

fun print_tree (tree, print_fun) = print_treehelp (tree, print_fun, "");