I don’t know if the abstract running time is 2n – 1 (or did you mean 2^{n – 1} or 2^n – 1? But we should we break this problem down in smaller solution steps. First you should write down (as I suppose you have) the type of the tree:

A number-tree is either: • a number OR • (pair number-tree number-tree) So this is a binary tree. A procedure sum-tree would either be called just once if the tree is just a number (its base case) or it would drill down into the left and right branches of it, that is, the first and second members of the pair. If we let a procedure called CALLS produce the total number of times SUM-TREE is called, then the non-base case of number-tree would make CALLS produce the value (+ (CALLS left) (CALLS right)), where left and right are, respectively, the first and second member of the pair. In mathematical notation we get the recurrence relation

cost(INPUT) = 1 if INPUT is just a number = (+ (cost LEFT) (cost RIGHT)) if INPUT is a (pair left right) Now we’d have to find a closed-form formula for this equation. Is this all clear so far? This is how we should approach these problems. This case might be pretty easy to solve, but most of such problems are VERY HARD to solve, so it’s interesting to practice the break down of such problems in very small parts.

What’s the purpose of this exercise? It is introducing you to the notion of abstract time; it’s also asking you to consider binary trees and find the shape of the tree that makes it costly to procedures like sum-tree; it’s also asking to find the shape of the tree that makes it more efficient to procedures like sum-tree.

You can put 4 numbers into a binary tree in many ways. For instance, you could be (pair 1 (pair 2 (pair 3 4))) or it could be (pair (pair 1 2) (pair 3 4)).

Computing sum-tree by hand, how many times it is called on each of these trees? Draw the shape of these trees on paper. What do you see? This is basically what this exercise is calling your attention to. Some shapes are worst-case to sum-tree and some are best-case.