What type of traversal should I use to find the sum of a binary tree?

Question

The next question appeared on a test that my teacher gave a couple of years ago. He gave an answer, but did not give a satisfactory explanation. I have this topic, but I have not found much. I was hoping the community would help me understand this concept.

To find the sum of all integers in a binary tree, what type of traversal will be used?

(A) wide


(B) depth in first order
(C) depth is the first post-order
(D) pre-order depth

My instructor says the answer is: (C) depth is first order, but I don’t understand why. It seems they will all work. I would appreciate an understanding that you might have.

Thanks.

Edit: I finally understood why my instructor thought the answer was (C).

If you were to write the sum function with the addition of all in one expression, for example:

int addup(Node n) { if (n == nil) return 0; return addup(n.left) + n.value + addup(n.right); } 

The workaround will be post-order regardless of the order of the members in total. This is because two functions are evaluated first before addition. However, coercion into order or a workaround is trivial, as Kate Randall showed in his answer.

Answer 1

Any traversal order will work, since the sum is associative and symmetric. For example, first order depth:

 int addup(Node n) { if (n == nil) return 0; int sum = addup(n.left); sum += n.value; sum += addup(n.right); return sum; } 

All passes allow for easy implementation of the amount.