loop through tree and sum all values in racket?

Question

I am try to write some generic method that takes two arguments (tree , function)to iterate over tree node and pass tree node to method for example i have this method called fold that take binary search tree as first argument and function as second argument while argument method takes four arguments (key value left-node-key right-node-key).

(define (fold tree function)
  (cond 
    [(null? tree) (function '() '() '() '())]
    [(number? (car tree))
     (+        (funct (car tree) (cadr tree) (caaddr tree) (car(cadddr tree)))
               (fold (cddr(caddr tree)) function)
               (fold (cddr(cadddr tree)) function)
               )]
    [else (function '() '() '() '())]

     )
    )

here is some methods that could be passed to above fold method : first method could be sumAll

(define (sumAll key value leftValue rightValue)
  (if (null? key) 
      0 
      (+ key leftValue rightValue) 
  )
)

second method could be findMinimum

(define (findMinimum key value leftValue rightValue)
  (if (null? key)
      '()
      (if (null? leftValue)
          key
          leftValue
      )
  )
)

use:

(define tr '(20 "20" (18 "18" ()(19 "19" () ())) (21 "21" (15 "15" () ()) ()) ))
(fold tr sumAll ) ; should return: 93
(fold tr findMinimum ) ; should return: 15

but i am getting this error from fold method:

+: contract violation
  expected: number?
  given: '()
  argument position: 2nd
  other arguments...:

any clue why i am getting this error.

assefamaru assefamaru · Accepted Answer · 2017-04-18T03:53:48

You can make fold abstract enough by accepting any procedure proc and a base case value init, and have the procedure apply the argument function over all nodes as follows:

(define (fold proc init lst)
  (cond
    [(null? lst) init]
    [else
     (proc (car lst)
           (fold proc init (caddr lst))
           (fold proc init (cadddr lst)))]))

Then, with the following binary search tree example definition:

(define BST '(20 "20" (18 "18" () (19 "19" () ())) (21 "21" (15 "15" () ()) ())))

you can use the procedure as:

(fold + 0 BST)                             ; find sum
=> 93
(fold min 1000 BST)                        ; find min
=> 15

loop through tree and sum all values in racket?

1 Answers