;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; define the datatype bintree, which is defined as
; (bintree) ::= (null)
;           ::= ( (symbol) (number) (bintree) (bintree) )
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define-datatype bintree bintree?
  (null)
  (node (key symbol?)
        (datum number?)
        (left bintree?)
        (right bintree?)
        )
  );end define datatype

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; tree is a bintree
;
; return the weight of the bintree
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define bintree-weight-sum
  (lambda (tree)
    (cases bintree tree
      (null() 0)
      (node (key datum left right)
            ( + datum (+ (bintree-weight-sum left) (bintree-weight-sum right))))
      );end cases
    );end lambda
  );end define

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; tree is a bintree
;
; pre-order traverse the tree and print out in list format.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define bintree-traverse
  (lambda (tree)
    (cases bintree tree
      (null () '() )
      (node (key datum left right)
            (cons datum (list (bintree-to-list left) (bintree-to-list right))))
      );end cases
    );end lambda
  );end define

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; tree is a bintree
;
; return the height of the tree
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define bintree-height
  (lambda (tree)
    (cases bintree tree
      (null () -1)
      (node (key datum left right)
            ( if( < (bintree-height left) (bintree-height right))
                (+ 1 (bintree-height right))
                (+ 1 (bintree-height left))
             );end if
            )
      );end cases
    );end lambda
  );end define