# [plt-scheme] HtDP exercise 29.1.1 | I don't understand ART.

If posting my answer to this problem violates the rules, I'm sorry,
please delete my mail; I can't explain myself properly without posting
it.
My answer to "What is the abstract running time?" is N. But this
doesn't agree with my intuition, since I believe this procedure to
have a faster growth rate than contains-doll?
I have the following data definition for a number tree,
;; exercise 29.1.1
; A number tree (short: nt) is either,
; 1. a number; or
; 2. (list nt nt)
Therefore, I have the following template,
(define (fun-for-nt ant)
(cond [(number? ant) ...]
[else ... (fun-for-nt (first ant)) ....
... (fun-for-nt (first (rest ant))) ...]))
Filling in the blanks for sum-tree, I obtain,
;; sum-tree : nt -> number
;; To compute the sum of all the numbers in a number tree
(define (sum-tree ant)
(cond [(number? ant) ant]
[else (+ (sum-tree (first ant))
(sum-tree (first (rest ant))))]))
;; examples
(check-expect (sum-tree 0) 0)
(check-expect (sum-tree 5) 5)
(check-expect (sum-tree (list 1 9)) 10)
(check-expect (sum-tree (list (list 3 4) 2)) 9)
(check-expect (sum-tree (list 7 (list 12 8))) 27)
(check-expect (sum-tree (list (list 1 5) (list 6 7))) 19)
So, I should measure the size of a number tree by the number of LISTs
it contains, since on meeting a LIST, I have to recur twice.
Therefore, for a number tree containing N (nested) LISTs, I have at
worst 2*N recursions to execute. But due to the discussion in the
text, I can fudge the constant 2 and say this has on the order of N
steps. Is all this correct? I think not. Can someone help me with
this?
Thanks for your time,
Horace.