University of Arizona, Department of Computer Science

CSc 120: Tree Sum (Recursive)

Expected Behavior

Write a recursive function tree_sum(tree), where tree is a binary tree, that returns the sum of the nodes in the tree.

Your function should work for empty trees, trees with one node, and trees with many nodes.

Note: Write a function and not a method.

Programming Requirements

Solve this problem using recursion.

Examples

In the examples below, the tree argument is illustrated by its string representation, however the actual argument is a tree object.

  1. tree_sum(tree) where tree is None
    return value: 0

  2. tree_sum(tree) where tree is (6 (8 None None) (9 None None))
    return value: 23

  3. tree_sum(tree) where tree is (6 (8 None None) (9 None (20 None None)))
    return value: 43

  4. tree_sum(tree) where tree is (6 (5 (8 None None) None) (7 None (9 None None)))
    return value: 35