# [plt-scheme] Help: I want to travel a binary tree?

 From: Matthias Felleisen (matthias at ccs.neu.edu) Date: Tue Jul 31 12:03:02 EDT 2007 Previous message: [plt-scheme] Help: I want to travel a binary tree? Next message: [plt-scheme] OpenGL + Linux Messages sorted by: [date] [thread] [subject] [author]

```Okay, I needed some fun for five minutes so I wrote down what I
recall about these traversal thingies. Perhaps one of them will
enlighten you. Note how I define what a tree is. -- Matthias

P.S. And don't ever, never use length to traverse a structure. Okay?

(define-struct node (left info right))
;; Tree = (make-node Tree Number Tree) | false

;; Tree ( [Promise [Listof Number]] Number [Promise [Listof
Number]] ) -> [Listof Number]
;; present the information nodes according in {pre, post, in}order
(define (traversal t order)
(define (traversal t)
(cond
[(node? t)
(order (delay (traversal (node-left t)))
(node-info t)
(delay (traversal (node-right t))))]
[else '()]))
(traversal t))

(define (pre-order-traversal t)
(traversal t (lambda (lft info rgt) (append (force lft) (list
info) (force rgt)))))

(define (post-order-traversal t)
(traversal t (lambda (lft info rgt) (append (force rgt) (list
info) (force lft)))))

(define (in-order-traversal t)
(traversal t (lambda (lft info rgt) (append (list info) (force
lft) (force rgt)))))

(require (lib "testing.ss" "htdp"))

(check-expect (pre-order-traversal (make-node false 1 false))
(list 1))
(check-expect (pre-order-traversal (make-node (make-node false 0
false) 1 false))
(list 0 1))
(check-expect (pre-order-traversal (make-node (make-node false 0
false) 1 (make-node false 2 false)))
(list 0 1 2))

(check-expect (post-order-traversal (make-node false 1 false))
(list 1))
(check-expect (post-order-traversal (make-node (make-node false 0
false) 1 false))
(list 1 0))
(check-expect (post-order-traversal (make-node (make-node false 0
false) 1 (make-node false 2 false)))
(list 2 1 0))

(check-expect (in-order-traversal (make-node false 1 false))
(list 1))
(check-expect (in-order-traversal (make-node (make-node false 0
false) 1 false))
(list 1 0))
(check-expect (in-order-traversal (make-node (make-node false 0
false) 1 (make-node false 2 false)))
(list 1 0 2))

(generate-report)

```

 Posted on the users mailing list. Previous message: [plt-scheme] Help: I want to travel a binary tree? Next message: [plt-scheme] OpenGL + Linux Messages sorted by: [date] [thread] [subject] [author]