(load library.clu)   ; you can comment this line out if you wish

(cluster BinTree
  ; Export: mkNode, mkTree, children?, label, leftchild, rightchild

  (rep lst)
  ; REP INVARIANT: The field lst is a list, containing either one or 3 elements
  ; if the list contains 3 elements, the first and last are trees.
  ; ABSTRACTION FUNCTION: for r: rep, if (lst r) is a singleton list,
  ; then r represents a leaf; otherwise r represents a tree with root
  ; (List$car (List$cdr (lst r))), left subtree (List$car lst r),
  ; and right subtree (List$car (List$cdr (List$cdr (lst r)))).

  (define mkNode (node)
    ; : Object -> BinTree
    ; EFFECT: return a leaf whose label is node
    (BinTree (List$cons node (List$nil))))

  (define mkTree (left node right)
    ; : BinTree*Object*BinTree -> BinTree
    ; EFFECT: return a tree whose left subtree is left, whose root is node,
    ; and whose right subtree is right
    (BinTree
     (List$cons left
      (List$cons node
       (List$cons right (List$nil))))))

  (define children? (tree)
    ; : BinTree -> Bool
    ; EFFECT: return true iff the tree has children
    (not (List$null? (List$cdr (lst tree)))))

  (define label (tree)
    ; : BinTree -> Object
    ; EFFECT: return the left subtree of tree
    (if (children? tree)
	(List$car (List$cdr (lst tree)))
      (List$car (lst tree))))

  (define leftchild (tree)
   ; : BinTree -> BinTree
   ; REQUIRES: tree has children
   ; EFFECT: return the left subtree of tree
   (if (children? tree)
       (List$car (lst tree))
     (error!-no-children)))  ; error: you violated the requirement (see above)

  (define rightchild (tree)
   ; : BinTree -> BinTree
   ; REQUIRES: tree has children
   ; EFFECT: return the right subtree of tree
   (if (children? tree)
       (List$car (List$cdr (List$cdr (lst tree))))
     (error!-no-children)))  ; error: you violated the requirement (see above)

)