This week's book giveaway is in the Cloud/Virtualizaton forum.We're giving away four copies of Mesos in Action and have Roger Ignazio on-line!See this thread for details.
Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Find sum of all leaves in a binary search tree

Prasanna Raman
Ranch Hand
Posts: 390
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
Posts: 390
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
Posts: 10417
63
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

Prasanna Raman
Ranch Hand
Posts: 390
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
Marshal
Posts: 21117
78
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

Prasanna Raman
Ranch Hand
Posts: 390
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
Marshal
Posts: 21117
78
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
Sheriff
Posts: 2974
123
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?

Prasanna Raman
Ranch Hand
Posts: 390
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
Sheriff
Posts: 2974
123
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.