aspose file tools*
The moose likes Beginning Java and the fly likes Find sum of all leaves in a binary search tree Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Find sum of all leaves in a binary search tree" Watch "Find sum of all leaves in a binary search tree" New topic
Author

Find sum of all leaves in a binary search tree

Prasanna Raman
Ranch Hand

Joined: Sep 05, 2010
Posts: 335
Hello,

I've implemented this in 2 ways. One method is traversing the tree in level order and the other method uses recursion. Please let me know which one is better in terms of time and space and also if there is a better way of implementing this.

Level-order method:



Recursion:

Prasanna Raman
Ranch Hand

Joined: Sep 05, 2010
Posts: 335
Prasanna Raman wrote:Hello,

I've implemented this in 2 ways. One method is traversing the tree in level order and the other method uses recursion. Please let me know which one is better in terms of time and space and also if there is a better way of implementing this.

Level-order method:







Recursion:

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Prasanna Raman wrote:I've implemented this in 2 ways. One method is traversing the tree in level order and the other method uses recursion. Please let me know which one is better in terms of time and space and also if there is a better way of implementing this.

Is there any particular reason you've posted almost the same source twice? I suggest you add any additional stuff to your original post with the 'Edit' button and remove that that 2nd one.

Also: you don't need to quote an entire post when you use the 'Quote' button. Just include the line (or lines) that are relevant.

However, in answer to your basic question: recursion is the normal way to deal with trees because you can generally re-use a lot of code, which makes things a lot shorter.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Prasanna Raman
Ranch Hand

Joined: Sep 05, 2010
Posts: 335
Hello Winston,

Thank you. Sorry, I was only trying to edit but clicked on the wrong option.

Coming to your response, I just read somewhere that this kind of recursion (since this is not tail recursive) takes up a lot of stack space and hence the iterative version might be better. Is that correct? If not, why is recursion better for trees? I see that the code is cleaner, but any other reason?
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18896
    
  40

Prasanna Raman wrote:
Thank you. Sorry, I was only trying to edit but clicked on the wrong option.

Coming to your response, I just read somewhere that this kind of recursion (since this is not tail recursive) takes up a lot of stack space and hence the iterative version might be better. Is that correct? If not, why is recursion better for trees? I see that the code is cleaner, but any other reason?



To be fair, not all tree data-structures have a parallel list connecting all the nodes. So, in most cases, you don't get to choose which is better.


As for me, I seem to heavily favor recursive as an algorithm -- perhaps it is from my period with Prolog -- so, I would choose recursion... for me, it is cleaner, and easier to understand. However, years ago, I implemented a recursive solution, and was told to remove it. Why? The code was part of an appliance, and given a large amount of data, and not enough stack, it would be possible to cause a stack overflow. When you are writing code of the operating system, and running in an appliance, that is an error that can't be tolerated... so I guess, that is another reason to avoid recursion.

Henry

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Prasanna Raman
Ranch Hand

Joined: Sep 05, 2010
Posts: 335
Thank you Henry. So in this case, what would be the running times and space complexity of the two? Does it take O(n) running time?
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18896
    
  40

Prasanna Raman wrote:Thank you Henry. So in this case, what would be the running times and space complexity of the two? Does it take O(n) running time?



Since each node is only visited once, I think it is safe to say that it is O(n). As for actual running times, you will need to measure it.

Henry
Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1128
    
  59

I am pretty sure you can optimise the recursive function you have so that it uses a constant Stack frame. I have one question though: What is a BinTreeNode? Is this a custom Type you've written yourself?


Tim Driven Development
Prasanna Raman
Ranch Hand

Joined: Sep 05, 2010
Posts: 335
Tim Cooke wrote: I have one question though: What is a BinTreeNode? Is this a custom Type you've written yourself?


Yes, Tom.

Here is the code:

Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1128
    
  59

I had an idea to rewrite the recursive function to be tail recursive which in some languages such as Scheme and Scala are optimised to occupy a fixed stack frame. But according to this thread Java does not provide that optimisation. Therefore it is not possible to improve on your current recursive solution.

So while your recursive function is the more elegant to look at, be aware that the stack frame usage is directly proportionate to the size of the tree. The iterative approach is more efficient in this case.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Find sum of all leaves in a binary search tree