# Determining external path length of a tree

• 08-31-2006
kolistivra
Determining external path length of a tree
Hi,

I'm studying algorithms from the book "Algorithms in C" by Sedgewick and I have encountered with a question that I couldn't solve. The problem is to create a function to determine the external path length of a tree. Here is the definition of external path length, if one needs: http://mathworld.wolfram.com/ExternalPathLength.html

• 08-31-2006
dwks
You could start at one side, counting the length up to and including NULLs, and then doing the other side.
• 08-31-2006
kolistivra
i have coded something like that:
Code:

```int epl(node *tree) {         if (tree==NULL) return 1;         else return epl(tree->left) + epl(tree->right) ; }```
but this gives 7 for the tree below,whereas it must give 6:
Code:

```          10         /    \       5      15     /  \    /    3    7  13```
did i code wrong? :S
• 08-31-2006
dwks
On rethinking the problem, I think it would be easier to count the root node rather than the NULL nodes. You might try this:
Code:

```int epl(node *tree) {         if (tree==NULL) return 1;         else return epl(tree->left) + epl(tree->right) ; }```
->
Code:

```int epl(node *tree) {         if (tree==NULL) return 0;         else return epl(tree->left) + epl(tree->right) + 1; }```
• 08-31-2006
kolistivra
Code:

```          10         /    \       5      15     /  \    /  \   3    7  13 17```
try your code on this. it will give 7, whereas it must give 8...
• 08-31-2006
quzah
So edit it to work right. Where's YOUR code? All I see is someone leeching off the effort of others.

Quzah.
• 08-31-2006
Yasir_Malik
Are you familiar with depth first search? This is an application of the algorithm.
• 08-31-2006
Yasir_Malik
Quote:

Originally Posted by kolistivra
Code:

```          10         /    \       5      15     /  \    /  \   3    7  13 17```
try your code on this. it will give 7, whereas it must give 8...

Shouldn't you expect 24? Perhaps I'm interpreting this problem incorrectly.
• 08-31-2006
pianorain
Quote:

Originally Posted by Yasir_Malik
Shouldn't you expect 24? Perhaps I'm interpreting this problem incorrectly.

Actually, I was expecting 25. According to the link, external path length is equal to the internal path length plus twice the number of nodes. I find the internal path length to be a bit more intuitive to calculate.
• 09-01-2006
Yasir_Malik
I calculated the internal path length as 10. So 7*2 + 10 = 24.
• 09-01-2006
kolistivra
@quzah: i wrote my code according to the suggestions of dwks,i think you didnt see it, and why im here is because im stuck at understanding and solving the question.

guys, i think my understanding of external path length turned out to be wrong :S but still, im trying to solve the problem according to "how i understood it", that is, the sum of all paths from the root to each external. for instance, im expecting 8 because :

10>5>3 = 2 steps
10>5>7 = 2 steps
10>15>13 = 2 steps
10>15>17 = 2 steps

in total = 8.

and this problem is what im trying to solve..

thanks all..
• 09-01-2006
Yasir_Malik
You're not including the null nodes, and you have to do it twice for the nodes with no children. Here's a better link:
http://planetmath.org/encyclopedia/E...athLength.html