# Finding the Internal Path Length (not work/school related)

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.
[code]
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)
{
return 0;
}

// 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);
}
[/code]
Is this proportional to N?

• Hi,

well, i think it is correct.
Cheers.
Alex

: 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.
: [code]
: 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)
: {
: return 0;
: }
:
: // 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);
: }
: [/code]
: Is this proportional to N?
:
: