A friendly place for programming greenhorns!
Find sum of all leaves in a binary search tree
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 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:

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
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?

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
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?

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
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 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:

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.
permaculture is largely about replacing oil with people. And one tiny ad:
RavenDB is an Open Source NoSQL Database thatâ€™s fully transactional (ACID) across your database
https://coderanch.com/t/704633/RavenDB-Open-Source-NoSQL-Database

This thread has been viewed 13100 times.

All times above are in ranch (not your local) time.
The current ranch time is
Jan 17, 2019 22:05:37.