Code

#lang racket

; set as binary tree

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

(define (make-tree entry left right)
  (list entry left right))

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set) 
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))


; converters

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

; tests

(define (adjoin-list-set xlist set)
  (define (iter xlist set)
  (if (null? xlist)
      set
      (iter (cdr xlist) (adjoin-set (car xlist) set))))
    (iter (reverse xlist) set))

(define tree1 (adjoin-list-set '(1 5 11 3 9 7) '()))
(define tree2 (adjoin-list-set '(11 5 9 1 7 3) '()))
(define tree3 (adjoin-list-set '(1 7 11 3 9 5) '()))

(tree->list-1 tree1)
(tree->list-1 tree2)
(tree->list-1 tree3)
(tree->list-2 tree1)
(tree->list-2 tree2)
(tree->list-2 tree3)

Output

'(1 3 5 7 9 11)
'(1 3 5 7 9 11)
'(1 3 5 7 9 11)
'(1 3 5 7 9 11)
'(1 3 5 7 9 11)
'(1 3 5 7 9 11)

Procedures produce the same results for every tree, namely sorted lists

tree->list-2

Time ~ \(O(m)\), where \(m\) - the number of all nodes \(n\) plus the number of empty leaves. For full binary tree: \(n=2^{h}-1\); \(m=2^{h+1}-1\), \(h\) - the height of the tree.

tree->list-1

It takes more time because of append for every left branch. Suppose that for append time ~ \(O(k)\) for a list of size \(k\). Total number of nodes in ALL left branches is \(\sum_{i=1}^{h}(2^{i}-1)=2^{h+1}-1-h\). So time ~ \(O(m)\) for both procedures, but the actual time is larger for tree->list-1.