How can you add memoization to the function nodeDepth()? How does this affect the worst-case running time of treeDepth()?
int
nodeDepth(int which, int *parent) {
if(parent[which] == -1) return 0;
else return 1 + nodeDepth(parent[which], parent);
}
int
treeDepth(int *parent, int num_nodes) {
int max_depth = -1;
for(int i = 0; i < num_nodes; i++) {
int i_depth = nodeDepth(i, parent);
if(i_depth > max_depth) max_depth = i_depth;
}
return max_depth;
}