; ---------- {SORTS} -----------------------------------------------------

TYPE 
   bintree = [nd];
   nd :: dontcare : STR 
         left : bintree 
         right : bintree;
ENDTYPE

; ---------- {FUNCTIONS} -------------------------------------------------

FUNC insert(at,a): bintree 
PRE ~(is-nd(a) && (at==dontcare(a)))
RETURN 
 if (
  ~ is-nd(a)                    -> nd(at,NIL,NIL),
  is-nd(a) && (at> dontcare(a)) -> nd(dontcare(a),left(a),insert(at,right(a))),
  is-nd(a) && (at< dontcare(a)) -> nd(dontcare(a),insert(at,left(a)),right(a)));

FUNC belongs(at,a): bool
RETURN 
 if (
  ~ is-nd(a)                    -> false,
  is-nd(a) && (at> dontcare(a)) -> belongs(at,right(a)),
  is-nd(a) && (at< dontcare(a)) -> belongs(at,left(a)),
  is-nd(a) && (at==dontcare(a)) -> true);

FUNC infix(a:bintree):STR-list
RETURN
 if is-NIL(a) 
    then <>
    else infix(left(a))^<dontcare(a)>^infix(right(a));

FUNC prefix(a:bintree):STR-list
RETURN
 if is-NIL(a) 
    then <>
    else prefix(left(a))^prefix(right(a))^<dontcare(a)>;