• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Find sum of all leaves in a binary search tree

 
Ranch Hand
Posts: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:

 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
reply
    Bookmark Topic Watch Topic
  • New Topic