Thread: Sum of depths in a binary tree.

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    122

    Sum of depths in a binary tree.

    I need to write a program to find the sum of depths of a binary tree, where a depth is by definition the shortest distance between a node and the root. I am required to code this using recursion.
    I was thinking of first coding a helper recursion to find the depth for each node. What would be the best way to do that?
    PS if I could move from the node to the root, I believe programming this helper recursion would not be very difficult. Is there a way to progress from the node to the root?

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    You can see here some code to get inspired. NOT to copy though ;p
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    But I do need the maximum depth, rather the sum of all minimum distances from each leaf to the root. Is there a way to reach the root from a certain leaf?

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Did you see how the function treedepth works? Can you get inspired a bit and give it a try?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    It's not quite what I am aiming at. My question is simple - by what means may I progress up a tree (from a given leaf to the root)?

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by peripatein View Post
    It's not quite what I am aiming at. My question is simple - by what means may I progress up a tree (from a given leaf to the root)?
    I suggest you NOT try to do that.

    Edit: I suggest stating in English what the function treedepth does.
    Then decide what part of that is not correct in solving the problem you are trying to solve. Then, write in English what needs to be done to solve your problem. Then, write the code.

    Tim S.
    Last edited by stahta01; 06-18-2013 at 03:30 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    If I give you a leaf node and you do not know the path that you have traversed to reach this leaf node, then you can not go to the root. Well, the root of the tree, is the same from which ever leaf node you have as starting point, isn't? Maybe you did not write the question as you really wanted.

    You need to think that the pointers of the tree go from top to bottom, thus you can not start from the leaf. You need to know the path.

    Again, by checking the link, or your notes I guess, you could see how the search for a leaf node works. Try searching for the given leaf node, but you should remember the path(store it somewhere~in a list, or in array with size the depth of a tree maybe~). Then, the length of the list or the cells of the array that are not empty, is what you are looking for I guess

    Tip: Asking for raw code, is simply unacceptable!
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by peripatein View Post
    It's not quite what I am aiming at. My question is simple - by what means may I progress up a tree (from a given leaf to the root)?
    Depends on how you built your tree and how you got to that leaf.

    If you got to that leaf through some recursive function, then you simply let the recursion fall back out. If you need to process all the nodes along the path starting at that leaf, going up to the root, simply add that processing after the recursive call (alternatively, you can process "on your way down" by adding the processing before you recurse to the child node).

    If you are at a leaf node and can't fall back up the stack to the root, then my suggestion would be to add parent pointers to each node in your tree, so you can easily go back up to the root. This requires managing the parent pointers on all inserts and deletes.

    You can also keep track of the nodes you went through on your way to the leaf (say, built when you call the lookup function) in an array or linked list, and follow that list back to the root, however I consider that less ideal.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by peripatein View Post
    It's not quite what I am aiming at. My question is simple - by what means may I progress up a tree (from a given leaf to the root)?
    As long as you can easily find the leaf when starting from the root, then the preferable way is to use recursion, processing each node after the recursive call.

    You would be best to not try and look for any other way.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Quote Originally Posted by iMalc View Post
    As long as you can easily find the leaf when starting from the root, then the preferable way is to use recursion, processing each node after the recursive call.

    You would be best to not try and look for any other way.
    I am not quite sure I follow. Did you suggest that I not retrace my steps after finding the desired leaf and that I simply search for that left, going through all the leaves, comparing the lengths of the paths each time?

  11. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    Okay, let's list the steps. If I'd like to find the sum of all depths, recursively, I could first create a function (perhaps another recursion) to find the depth of each leaf, and then call upon that function/recursion within my main recursion to perform the actual summation. Would you agree?

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by peripatein View Post
    I am not quite sure I follow. Did you suggest that I not retrace my steps after finding the desired leaf and that I simply search for that left, going through all the leaves, comparing the lengths of the paths each time?
    Not exactly. You don't "retrace your steps", the recursion does that for you. What do you mean all leaves?

    Quote Originally Posted by peripatein View Post
    Okay, let's list the steps. If I'd like to find the sum of all depths, recursively, I could first create a function (perhaps another recursion) to find the depth of each leaf, and then call upon that function/recursion within my main recursion to perform the actual summation. Would you agree?
    I would not do it as a list of steps. To solve the very odd problem you have, I would refactor the question into a recurrence relation. Then I would translate that into a single recursive function that examines each node only once.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  3. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  4. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2003, 12:47 AM
  5. b-tree (not binary tree) implementation help
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 01-02-2002, 03:30 PM