how do you sum tree in scheme

Question

;; A [BT X] is one of 
;; - 'leaf
;; - (make-node X [BT X] [BT X])


(define-struct node (val left right))
;; interpretation: represents a node with a value
;; a left and right subtree

(define (tree-sum tree)
   (cond 
      [(symbol=? tree 'leaf) ...] ;; the value remains same 
      [(node? tree)
            (+ (tree-sum (node-val tree))
               (tree-sum (node-left tree))
               (tree-sum (node-right tree)))]))

not quite sure if i'm on the right track.

Normally, A pair tree is either

a leaf (not a pair), or
a pair, whose car and cdr values are pair-trees.

recursive summing procedure will have to deal with these two cases:

a numbers, i.e., leaves of a tree of numbers, and
pairs, in which case it should sum the left and right subtrees, and add those sums together.

Therefore,

(define (pair-tree-sum pair-tree)
    (cond 
       [(number? pair-tree)
             pair-tree]
       [else
             (+ (pair-tree-sum (car pair-tree))
                (pair-tree-sum (cdr pair-tree)))]))

@Jack i'm still writing the codes. just thinking if it is better to do the summation in an accumulation style. — ads27
if the tree is simply a list of numbers, that will be much easier. However, it is a complex structure. — ads27
Are you asking about summing a BT tree, a tree represented as nested lists, or just asking whether you should use an accumulator? — molbdnilo
@molbdnilo is there a way that we can turn all the numbers on the tree into a list? — ads27

Jack Jack · Accepted Answer · 2014-11-24T01:40:36

You can split the function into two parts - one that converts the tree into a list of numbers, and another that just uses foldl with that list, and foldl has the advantage of automatically doing the summation as an accumulator.

(define (tree->list tree)
  (if (pair? tree)
      (append (tree->list (car tree))
              (tree->list (cdr tree)))
      (list tree)))

(define (tree-sum tree)
  (foldl + 0 (tree->list tree)))

how do you sum tree in scheme

1 Answers