University of Arizona, Department of Computer Science

CSc 120: Tree Height (Recursive)

Expected Behavior

Write a recursive function tree_height(tree), where tree is a binary tree, that returns the height of the tree. Recall that the height of a tree is the maximum of the levels of the nodes in the tree (or, the length of the longest path 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_height(tree) where tree is None
    return value: 0

  2. tree_height(tree) where tree is (6 (8 None None) (9 None None))
    return value: 1

  3. tree_height(tree) where tree is (6 (8 None None) (4 None (2 None (9 None None))))
    return value: 3

  4. tree_height(tree) where tree is (6 (2 (3 (8 None None) None) (4 None None)) (9 None (12 (5 None None) (16 None (14 None None)))))
    return value: 4