問題2-63(a) (2.3.3 Example: Representing Sets)

今度は集合をbinary treeで構成するお話で、でも2-63はbinary treeを配列に変換する関数についての問題という。。
どれも{1,3,5,7,9,11}という集合をbinary treeで表現したものですが、

(define first 
  (make-tree 7
	     (make-tree 3
			(make-tree 1 '() '())
			(make-tree 5 '() '()))
	     (make-tree 9
			'()
			(make-tree 11 '() '()))))

(define second
  (make-tree 3
	     (make-tree 1 '() '())
	     (make-tree 7
			(make-tree 5 '() '())
			(make-tree 9
				   '()
				   (make-tree 11 '() '())))))

(define third
  (make-tree 5
	     (make-tree 3
			(make-tree 1 '() '())
			'())
	     (make-tree 9
			(make-tree 7 '() '())
			(make-tree 11 '() '()))))

tree->list-1，tree->list-2どちらでも、どの表現に対しても(1 3 5 7 9 11)という出力が得られてとてもよかったですね。
tree->list-1はappendとcons、tree->list-2はconsでリストを構成していっているんだけど、append、consどちらも第1引数が結果のリストの左側になる。そしてtree->list-1、tree->list2ともに左部分木、エントリ、右部分木という順のリストに変換するので、同じ結果は得られるはz

(b)に関してはどうも同じ計算量に見えたりするんですけど、どの粒度でこの問題考えればいいんだろう。