Answer: Memoization

Question: How can you add memoization to the function nodeDepth()? How does this affect the worst-case running time of treeDepth()?

Answer:

int
nodeDepth(int which, int *parent, int *depth) {
    if(depth[which] != -1) return depth[which];

    if(parent[which] == -1) depth[which] = 0;
    else depth[which] = 1 + nodeDepth(parent[which], parent, depth);

    return depth[which];
}

int
treeDepth(int *parent, int num_nodes) {
    int depth = new int[num_nodes];
    for(int j = 0; j < num_nodes; j++) depth[j] = -1;

    int max_depth = -1;
    for(int i = 0; i < num_nodes; i++) {
        int i_depth = nodeDepth(i, parent, depth);
        if(i_depth > max_depth) max_depth = i_depth;
    }
    delete[] depth;
    return max_depth;
}