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

(cluster Tree
  ; Export: make, empty, empty?, left, right, root

  (rep defined l n r)
  ; REP INVARIANT: The field defined is either 0 or 1 and if the field defined
  ; is 1, then the fields l and r hold Trees.
  ; ABSTRACTION FUNCTION: for r: rep, if (defined r) is 0, then r represents
  ; the empty tree, otherwise r represents the tree with left subtree (l r),
  ; root (n r), and right subtree (r r).

  (define empty ()
    ; : -> Tree
    ; EFFECT: return an empty tree
    (Tree 0 0 0 0))

  (define make (left node right)
    ; : Tree, object, Tree -> Tree
    ; EFFECT: return a tree with left subtree left, root node,
    ; and right subtree right
    (Tree 1 left node right))

  (define empty? (tree)
    ; : Tree -> Bool
    ; EFFECT: return true iff tree is empty
    (= 0 (defined tree)))

  (define left (tree)
   ; : Tree -> Tree
   ; REQUIRES: tree is not empty
   ; EFFECT: return the left subtree of tree
   (if (defined tree)
       (l tree)
     (error!-not-defined))) ; error: you violated the requirements (see above)

  (define root (tree)
   ; : Tree -> Object
   ; REQUIRES: tree is not empty
   ; EFFECT: return the root of tree
   (if (defined tree)
       (n tree)
     (error!-not-defined))) ; error: you violated the requirements (see above)

  (define right (tree)
   ; : Tree -> Tree
   ; REQUIRES: tree is not empty
   ; EFFECT: return the right subtree of tree
   (if (defined tree)
       (r tree)
     (error!-not-defined))) ; error: you violated the requirements (see above)
)

(define leaf-make (node)
  ; : Object -> Tree
  ; EFFECT: return a tree whose root contains node and whose subtrees are empty
  (Tree$make
    (Tree$empty) node (Tree$empty)))