bbtreeutils.scm

;; general tree fold
(define (traverse traverser nil tree)
  (define (left nil)
    (traverse traverser nil (node-left tree)))
  (define (right nil)
    (traverse traverser nil (node-right tree)))
  (if (empty? tree)
      nil
      (traverser (node-key tree)
                 (node-key value)
                 left
                 right
                 nil)))

(define (l-to-r-in-order cons nil tree)
  (traverse (lambda (k v l r n)
              (r (cons k v (l n))))
            nil
            tree))

(define (r-to-l-in-order cons nil tree)
  (traverse (lambda (k v l r n)
              (l (cons k v (r n))))
            nil
            tree))

(define (l-to-r-post-order cons nil tree)
  (traverse (lambda (k v l r n)
              (cons k v (r (l n))))
            nil
            tree))