The only difference between depth-first and breadth-first search is the difference between append and prepend. Herewe see breadth-fi rst-searchinaction:

> (breadth-first-search 1 ( i s 12) 'binary-tree)

;; Search: (1)

;; Search: (2 3)

;; Search: (3 4 5)

;; Search: (4 5 6 7)

;; Search: (5 6 7 8 9)

;; Search: (6 7 8 9 10 11)

;; Search: (7 8 9 10 11 12 13)

;; Search: (8 9 10 11 12 13 14 15)

;; Search: (9 10 11 12 13 14 15 16 17)

;; Search: (10 11 12 13 14 15 16 17 18 19)

;; Search: (11 12 13 14 15 16 17 18 19 20 21)

;; Search: (12 13 14 15 16 17 18 19 20 21 22 23)

12