copy-tree-sum


The copy-tree-sum problem wants a function accepting an integer tree and returning a copy of the tree with all integers replaced by the sum of the integers in the original tree.

 guile> (copy-tree-sum 1) 
 1 
 guile> (copy-tree-sum '(1 . (2 . 3))) 
 (6 6 . 6) 
 guile> 

A solution guided by structural recursion over the tree is a snap:

 (define (copy-tree-sum tree) 
  
   ; Return a copy of the given tree with all integers replaced by the sum of 
   ; the integers in the given tree. 
  
   (define (sum-tree tree) 
     (if (pair? tree) 
       (+ (sum-tree (car tree)) (sum-tree (cdr tree))) 
       tree)) 
  
   (let ((total (sum-tree tree))) 
     (let cts ((t tree)) 
       (if (pair? t) 
         (cons (cts (car t)) (cts (cdr t))) 
         total)))) 

This solution makes two passes over the given tree. Is a one-pass solution possible? (This solution has other problems too, most of them stemming from the simple-minded view of trees as pairs; these other problems are not of interest in this note.)

A one-pass solution is tricky because of the dependency between computing the sum and copying the tree: the tree-copy has to be done after the sum has been computed. A one-pass solution requires somehow breaking the dependency.

One way to break the dependency is to remember how the tree is structured while computing the sum. One pass through the given tree results in the total and a representation of the tree structure, which can be used, along with the total, to create a tree copy.

In Scheme, the simplest way to represent a tree is by a procedure that builds the tree. Calling the procedure with the sum results in a tree copy with the appropriate value.

 (define (copy-tree-sum tree) 
  
   ; Return a copy of the given tree with the leaf nodes replaced by the sum of 
   ; the leaf nodes in the given tree. 
  
   (let ((result (copy-tree-sum' tree))) 
     ((car result) (cdr result)))) 
  
  
 (define (copy-tree-sum' tree) 
  
   ; Return a pair, the first element of which is a function building a copy of 
   ; the given tree and the second element of which is the sum of the values in 
   ; the given tree. 
  
   (if (pair? tree) 
  
     (let 
  
       ((l (copy-tree-sum' (car tree))) 
        (r (copy-tree-sum' (cdr tree)))) 
  
       (cons 
  
         (lambda (total) 
           (cons ((car l) total) 
                 ((car r) total))) 
  
         (+ (cdr l) (cdr r)))) 
  
     (cons 
  
       (lambda (total) total) 
  
       tree))) 

category-code