The question was: Write a recursive program that computes the internal path length of a binary tree in time proportional to the number of nodes in the tree.
I have the program, but I'm not sure if it meets the criteria.
int GetInternalPathLength (link root, int curLevel = 0)
// Check if this node is external. If it is,
// don't count its level as part of the IPL.
if (root -> leftChild == NULL && root -> rightChild == NULL)
// Add this node's level and the IPL of it's
// subtrees to the TOTAL IPL.
return curLevel +
GetInternalPathLength (root -> leftChild, curLevel + 1) +
GetInternalPathLength (root -> rightChild, curLevel + 1);
Is this proportional to N?
0 · ·