#!/usr/bin/env guile --debug -ds
!#

; * Rick van der Zwet
; * 0433373
; * Scheme programming assigment 1a
; * Licence: BSD
; * $Id: exercise2.scm 378 2007-12-11 16:14:47Z rick $

;infix order (<left-tree> <node> <right-tree>), in breadth first order
;just seems to see the fact we are 'pushing' the node and then
;traversing the tree

(define treewalking
    (lambda (tree)
;        (display "Debug  : ")
;        (display tree)
;        (newline)
;        (display "Length : ")
;        (display (length tree))
;        (newline)
        ;when nothing left on the stack bail out
        (if (null? tree) tree
            (cond
                ;emtry branch, continue
                ((null? (car tree))
                    (treewalking (cdr tree))
                )
                ;leaf, add and continue
                ((symbol? (caar tree))
                    (cons
                        (caar tree)
                        (treewalking (cdr tree))
                    )
                )
                (else
                    ; fetch the node
                    ; check wether we still have an tail
                    (if (null? (cdr tree))
                        (cons
                            (cadar tree)
                            ; recurse with left, right
                            (treewalking (cons (caar tree)
                                               (cddar tree)
                                         )
                            )
                        )
                        (cons
                            (cadar tree)
                            ; recurse with tail, left, right
                            (treewalking (append (cdr tree)
                                               (cons (caar tree)
                                                     (cddar tree)
                                               )
                                         )
                            )
                        )
                    )
                )
            )
        )
    )
)

(define treewalk
    (lambda (tree)
        (treewalking (list tree))
    )
)

(display
    (equal?
        (treewalk
            '( (b) a ( ((f) d (g)) c (() e (h)) ) )
        )
        '(a b c d e f g h)
    )
)