## Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 786

This Forum Only

Finding the Internal Path Length (not work/school related) Posted by cnsr on 2 Feb 2004 at 8:39 PM
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)
{
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);
}
```

Is this proportional to N?

Re: Finding the Internal Path Length (not work/school related) Posted by athomas on 29 Mar 2004 at 1:05 PM
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.
:
```: 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);
: }
: ```

: Is this proportional to N?
:
:

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic