Thread: Determining external path length of a tree

  1. #1
    Registered User
    Join Date
    Jul 2006
    Posts
    25

    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

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    You could start at one side, counting the length up to and including NULLs, and then doing the other side.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    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

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    Code:
              10
            /    \
          5      15
        /   \    /   \
       3     7  13 17
    try your code on this. it will give 7, whereas it must give 8...

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    So edit it to work right. Where's YOUR code? All I see is someone leeching off the effort of others.


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    Are you familiar with depth first search? This is an application of the algorithm.

  8. #8
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    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.

  9. #9
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  10. #10
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    I calculated the internal path length as 10. So 7*2 + 10 = 24.

  11. #11
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    @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..

  12. #12
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. VC++ a POS
    By Welder in forum Windows Programming
    Replies: 40
    Last Post: 11-07-2007, 03:07 PM
  3. Weight Balanced Tree - Implementation
    By paulovitorbal in forum C Programming
    Replies: 1
    Last Post: 10-31-2007, 02:28 PM
  4. problem in creating a tree
    By Lorin_sz in forum C++ Programming
    Replies: 2
    Last Post: 09-26-2005, 01:28 PM
  5. Unresolved external symbols in OGL
    By Shadow12345 in forum Game Programming
    Replies: 4
    Last Post: 08-04-2002, 09:46 PM