A binary search tree is a binary tree satisfying the following property: for each node in the tree, the key stored in the node is greater than or equal to every key stored in the left child of the node and less than or equal to every key stored in the right child of the node. In other words, a binary tree is a binary search tree if a pre-order traversal encounters a sequence of keys ordered ascendingly (according to some ordering on keys). In practice, binary search trees are commonly employed to represent sets and maps.

The following declaration introduces a datatype bstree for binary search trees in which the stored keys are strings:

It should be noted that not every value of the type bstree represents a valid binary search tree as it is certainly possible to construct a value representing a binary tree but not a binary search tree.

The following function [bstree_inord] does a in-order traversal of a given binary tree:

fun bstree_inord ( t0: bstree, fwork: string -<cloref1> void ) : void = ( case+ t0 of | E () => () | B (t1, k, t2) => { val () = bstree_inord (t1, fwork) val () = fwork (k) val () = bstree_inord (t2, fwork) } ) (* end of [bstree_inord] *)

If [t0] is a binary search tree, then the sequence of keys processed by [fwork] are ordered ascendingly.

Given a binary search tree and a key, the following function [bstree_search] checks whether the key is stored inside the tree:

fun bstree_search ( t0: bstree, k0: string ) : bool = ( // case+ t0 of | E () => false | B (t1, k, t2) => let val sgn = compare (k0, k) in case+ 0 of | _ when sgn < 0 => bstree_search (t1, k0) | _ when sgn > 0 => bstree_search (t2, k0) | _ (*k0 = k*) => true end // end of [B] // ) (* end of [bstree_search] *)

Note that [bstree_search] returns true if the given key is found. Otherwise, it returns false.

Given a binary search tree and a key, the following function [bstree_insert] inserts the key into the tree:

fun bstree_insert ( t0: bstree, k0: string ) : bstree = ( // case+ t0 of | E () => B (E, k0, E) | B (t1, k, t2) => let val sgn = compare (k0, k) in case+ 0 of | _ when sgn < 0 => B (bstree_insert (t1, k0), k, t2) | _ when sgn > 0 => B (t1, k, bstree_insert (t2, k0)) | _ (*k0 = k*) => t0 // [k0] found and no actual insertion end // end of [B] // ) (* end of [bstree_insert] *)

Note that [bstree_insert] inserts the key only if it is not already stored inside the given tree. Also, if inserted, the key is always stored in a newly created leaf node.

Please find on-line the entirety of the code in this section plus some additional code for testing.