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

thanks in advance

You could start at one side, counting the length up to and including NULLs, and then doing the other side.

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

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;
}

---

Code:

---

          10
        /    \
      5      15
    /  \    /  \
  3    7  13 17

---

try your code on this. it will give 7, whereas it must give 8...

So edit it to work right. Where's YOUR code? All I see is someone leeching off the effort of others.


Quzah.

Are you familiar with depth first search? This is an application of the algorithm.

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.

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.

I calculated the internal path length as 10. So 7*2 + 10 = 24.

@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..

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