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.

Functions which take (('a * 'a) -> order) functions behave as Int.compare does:

compare (i, j)

returns LESS, EQUAL, or GREATER when i is less than, equal to, or greater than j, respectively.

list

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

traversal order

LNR would produce: ABCDEFGHI
RNL would produce: IHGFEDCBA

In-order LNR

Reverse in-order RNL

 datatype traversal_order = LNR | RNL

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

Remove contains the most challenging aspect of this studio. When instructed to remove a node from a tree, there are several cases:

not found

What will indicate that you reached the point where you know the node is not found in the tree?
note: this has a trivial solution.

no child in the left tree

How will you detect this pattern?
note: this has a trivial solution.

no child in the right tree

how will you detect this pattern?
note: this has a trivial solution.

no children are present

If you need to remove a node and it has both children, now you have a legit problem. You must maintain a correct binary search tree.

A common approach is to choose one of the following:

• remove the right most descendant in the left child, and promote it to be the node at the current level, or
• remove the left most descendant in right left child, and promote it to be the node at the current level

The image below shows finding the left most child in the right subtree for promotion:

Building a helper function will likely be helpful.

Wikipedia BST Deletion

note: this function is curried.

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

find

reference: List.find

note: this function is curried.

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

fun

to_first_and_last

This function is useful for find_order_hof and fold_order_hof.

It simply returns the left and right tree as a 2-tuple in the appropriate order based on the specified traversal_order.

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

The intention is that, once correctly implemented, you can use it in find_order_hof and fold_order_hof with something akin to:

val (first,last) = to_first_and_last(order, left, right)

find_order_hof

reference: List.find

Instead of a binary search style find, here we create a find based on a traversal order and a predicate. It returns the first item node value it encounters which passes the predicate function.

note: this function is curried.

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

fold_order_hof

reference: List.foldl

note: this function is curried.

fun fold_order_hof (order:traversal_order) (f : 'a * 'b -> 'b) (init : 'b) (t : 'a tree) : 'b = 
    raise NotYetImplemented

fun fold_lnr f init t = 
   fold_order_hof LNR f init t
fun fold_rnl f init t = 
   fold_order_hof RNL f init t

filter (Not Required)

reference: List.filter

note: this function is curried.

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

filter_civil_war_style

This function is much like filter, only instead of deftly omitting the nodes which do not pass the predicate, it lops off the entire subtree of those nodes which do not pass the predicate.

note: this function is curried.

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

map_to_tree_of_questionable_validity

reference: List.map

This function converts the specified 'a tree into a 'b tree. It is unreasonable to expect the resulting tree (which is to have the same structure as the specified 'a tree) will be a valid binary search tree.

note: this function is curried.

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

map_to_tree_hof (Not Required)

note: this function is curried.

fun map_to_tree_hof (order:traversal_order) (compare_function:(('b * 'b) -> order)) (f : 'a -> 'b) (t : 'a tree) : 'b tree =
    raise NotYetImplemented

fun map_to_tree_lnr compare_function f t = 
   map_to_tree_hof LNR compare_function f t
fun map_to_tree_rnl compare_function f t = 
   map_to_tree_hof RNL compare_function f t

map_to_list_hof (Not Required)

note: this function is curried.

fun map_to_list_hof (order:traversal_order) (f : 'a -> 'b) (t : 'a tree) : 'b list =
   raise NotYetImplemented

fun map_to_list_lnr f t = 
   map_to_list_hof LNR f t
fun map_to_list_rnl f t = 
   map_to_list_hof RNL f t

Applications

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

Be sure to use BinaryTree.LEAF and BinaryTree.BRANCH.

Alternatively, use open BinaryTree to pollute your namespace so that you can use BRANCH and LEAF.

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

file:	unit_test_binary_tree_and_apps.sml
source folder:	src/test/sml/binary_tree

Pledge, Acknowledgments, Citations

file:

studio-binary-tree-pledge-acknowledgments-citations.txt

More info about the Honor Pledge