Binary Search Tree Assignment

We will implement a binary search tree data structure as well as a few Higher Order Function Hall of Fame inductees.

Background

order

SML's General structure's order

datatype order = LESS | EQUAL | GREATER

Values of type order are used when comparing elements of a type that has a linear ordering.

list

We will implement some of the higher ordered functions list provides on our binary tree.

traversal order

In-order LNR

Reverse in-order RNL

 datatype traversal_order = LNR | RNL

For the tree below LNR would produce ABCDEFGHI and RNL would produce IHGFEDCBA.

BinaryTree

file:	src/main/sml/binary_tree/binary_tree.sml
functions:	insert remove find ...

datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree

core

insert

note: this function is curried

fun insert (compare_function:(('a * 'a) -> order)) (t:'a tree) (item:'a) : 'a tree = 
    raise NotYetImplemented

remove

fun remove (equal_less_greater_function:'a -> order) (t:'a tree) : 'a tree =
    raise NotYetImplemented

find

reference: List.find

fun find (equal_less_greater_function : 'a -> order) (t:'a tree) : 'a option = 
    raise NotYetImplemented

fun

to_first_and_last

fun to_first_and_last(order:traversal_order, left:'a tree, right:'a tree) =
    raise NotYetImplemented

find_order_hof

fun find_order_hof (order:traversal_order) (predicate:'a->bool) (t:'a tree) : 'a option =
    raise NotYetImplemented

fun find_lnr (predicate:'a->bool) (t:'a tree) : 'a option = 
   find_order_hof LNR predicate t
fun find_rnl (predicate:'a->bool) (t:'a tree) : 'a option = 
   find_order_hof RNL predicate t

map

reference: List.map

fun map(f : 'a -> 'b, t : 'a tree) : 'b tree = 
    raise NotYetImplemented

filter

reference: List.filter

fun filter(predicate : 'a -> bool, t : 'a tree) : 'a tree = 
    raise NotYetImplemented

find_lnr

reference: List.find

reference: In-order traversal

fun find_lnr(predicate : 'a -> bool, t : 'a tree) : 'a option =
    raise NotYetImplemented

fold_lnr

reference: List.foldl

reference: In-order traversal

fun fold_lnr(f : 'a * 'b -> 'b, init : 'b, t : 'a tree ) : 'b = 
    raise NotYetImplemented

Application

file:	src/main/sml/binary_tree/apps_using_binary_tree.sml
functions:	max_height sum_int_tree ...

max_height

fun max_height(t : 'a BinaryTree.tree) : int = 
 	raise NotYetImplemented

sum_int_tree

fun sum_int_tree(t : int BinaryTree.tree) : int =
 	raise NotYetImplemented

Testing

binary_tree/unit_test_binary_tree.sml