square numbers in a tree using fold

Question

The aim is to produce a tree with all the numbers squared using a fold-tree function. This is not homework, by the way. So I can discuss it freely.

; A Tree-Of-Numbers is one of:
; - (make-node Tree-Of-Numbers Number Tree-Of-Numbers)
; - EmptyTree
; interp. a tree with numbers stored at its nodes.

(define-struct node (left value right))

; An EmptyTree is a structure (make-empty-tree))
; interp. an empty tree

(define-struct empty-tree ())

(define EXAMPLE-TREE
  (make-node (make-node (make-node EMPTY 6 EMPTY)
                        20 EMPTY) 8 (make-node (make-node EMPTY 14 EMPTY)
                        42 (make-node EMPTY 2 EMPTY))))

(define EMPTY (make-empty-tree))

I have programmed a fold-tree function:

(define (fold-tree f b tree)
  (cond
    [(empty-tree? tree) b]
    [else (f (node-value tree)
             (fold-tree f b (node-left tree))
              (fold-tree f b (node-right tree)))]))

Now I have to use this function to square all numbers in a tree. I can do this in other ways, for instance so:

(define (sqr-tree tree)
  (cond
    [(empty-tree? tree) EMPTY]
    [(node? tree) (make-node (sqr-tree (node-left tree))
                                 (sqr (node-value tree))
                                 (sqr-tree (branch-right tree)))]))

I have also been able to do this by writing a map-tree function and using that to square all numbers in a tree. But the question is, how to do this using fold-tree?

Answer 1

Assuming all the helper procedures are correct, this should work:

(define (sqr-tree tree)
  (fold-tree (lambda (value left right)
               (make-node left (sqr value) right))
             EMPTY
             tree))