Finding the Internal Path Length (not work/school related) - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

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

cnsrcnsr Posts: 1Member
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?

Comments

  • athomasathomas Posts: 228Member
    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?
    :
    :

Sign In or Register to comment.