F4. Tree Depth

Problem: Tree Depth
Given: A rooted tree with a set of edges E and n vertices represented by 0..n-1, with 0 being the root. Each edge in E will be downward: i.e., pointing away from the root.
Produce: A function that returns the depth of the tree, where the depth of a tree is the maximum length of any path from the root of the tree to a leaf.

For example:

  • The depth of (5, {(0, 1), (0, 2), (2, 3), (2, 4)}) is 2.
  • The depth of (5, {(0, 1), (1, 2), (2, 3), (3, 4)}) is 4.

Hint: You may want to start by drawing the example trees. This function is way easier to write recursively than iteratively.

Last modified: Thursday, 10 July 2014, 5:38 PM