scheme-test-programs/lists/tree-sort.scm

(define (make-node value) (list 'node value #f #f))
(define (node-value t) (cadr t))
(define (left-branch t) (caddr t))
(define (right-branch t) (cadddr t))  
(define (set-left-branch! t v) (set-car! (cddr t) v) t)
(define (set-right-branch! t v) (set-car! (cdddr t) v) t)

(define (insert value root)
  (cond ((not root)
	 (make-node value))
	((< value (node-value root))
	 (set-left-branch! root (insert value (left-branch root))))
	(else
	 (set-right-branch! root (insert value (right-branch root))))))

(define (leaves root rest)
  (if (not root)
      rest
      (leaves (left-branch root)
	      (cons (node-value root)
		    (leaves (right-branch root)
			    rest)))))

(define (tree-sort l)
  (leaves (fold #f insert l) '()))