Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


(define (preorder tree)
  (if (null? tree)
      '()
      (append (list (car tree))
              (preorder (cadr tree))
              (preorder (caddr tree)))))
 
(define (inorder tree)
  (if (null? tree)
      '()
      (append (inorder (cadr tree))
              (list (car tree))
              (inorder (caddr tree)))))
 
(define (postorder tree)
  (if (null? tree)
      '()
      (append (postorder (cadr tree))              
              (postorder (caddr tree))
              (list (car tree)))))
 
(define (level-order tree)
  (define lst '())
  (define (traverse nodes)
    (if (pair? nodes)
        (let ((next-nodes '()))
          (do ((p nodes (cdr p)))
              ((null? p))
            (set! lst (cons (caar p) lst))
            (let* ((n '())
                   (n (if (null? (cadar p))
                           n
                           (cons (cadar p) n)))
                   (n (if (null? (caddar p))
                           n
                           (cons (caddar p) n))))
              (set! next-nodes (append n next-nodes))))
          (traverse (reverse next-nodes)))))
  (if (null? tree)
      '()
      (begin
        (traverse (list tree))
        (reverse lst))))
 
(define (demonstration tree)
  (define (display-values lst)
    (do ((p lst (cdr p)))
        ((null? p))
      (display (car p))
      (if (pair? (cdr p))
          (display " ")))
    (newline))
  (display "preorder:    ") (display-values (preorder tree))
  (display "inorder:     ") (display-values (inorder tree))
  (display "postorder:   ") (display-values (postorder tree))
  (display "level-order: ") (display-values (level-order tree)))
 
(define the-task-tree
  '(1 (2 (4 (7 () ())
            ())
         (5 () ()))
      (3 (6 (8 () ())
            (9 () ()))
         ())))
 
(demonstration the-task-tree)