• 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

how to write inorder-method for trees?

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello to everyone,

I have a question related to trees in Java. The following code is given:



The inorder-method is the one that really imports. I have to go through a tree using the Inorder-method. I do understand how this works, however I don't understand how the code fits to the inorder process. I understand the code up to the point where it reaches the most left "root", but then I do not know how to go further. How do I reach the root above then?
I would be very happy if someone can help me! :-)
Best, Juna
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Juna,

well, first of all you should have some Nodes ready.
Then, I assume you have, say, a variable called
rootBinarySearchTree, with your root Node as element, and
of type BinarySeachTree. If not, then create one.

Next, have you tested: rootBinaryTree.printInorder()?
Did it indeed print out the Node tree, in inorder sequence?

If so, then notice the recursion that is being used here.
When the 'leftmost' leaf has been printed, the method has finished,
and so it returns to the calling method, which is that of the parent Node.

So, in effect, you do not have to do anything special, the recursion
takes care of it all.

A handy way is always to put some println()'s at strategic places,
so that you can follow what is going on. For instance,

So, try this out and see if you can follow what is going on.

Greetz,
Piet
 
Juna Burk
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Piet,

thanks a lot for your help! I think I got it :-)

Best,
Juna
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Juna,

you're welcome! Glad I could help.

Greetz,
Piet
 
Juna Burk
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello,

I though have another question concerning this code. In case "right.printInorder()" at the bottom of the code is used on a root that is null, it says "root is null, nothing to print, so just returning". Then it continues with "Now printing the root itself" and prints the root that is the parent of the former one.
I understand the logic because I know that this root now has to be printed if the leftChild is null. However I do not understand why, after haveing passed the return- statement, the code continues with "Now printing the root itself". Can someone explain this to me please?

Best, Juna
 
Bartender
Posts: 1845
10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think what you need to help you see what is happening is an indication of what level of nesting the current message is coming from.
Maybe add a parameter to your print in order method to indicate what level of the tree you are at?


The following tree would give output like you describe.



After it prints the node "left1Right2" it has finished printing the left1 subtree, so the next one it would print is the Root.

 
Juna Burk
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for your answer! :-) Ok, so I understand the logic behind it now. However I do not understand how the code fits the logic. Why is the root printed after the return-statement? What does return do? I thought it ends the method abruptly and continues with "System.out.println("root is "+ root);", but it's not like that. But why?
 
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think what's messing you up is the fact that Node is wrapped in a BinarySearchTree, which is what has the printInOrder() method. I suppose it's reasonable to do it this way because you could add two other methods to implement pre-order and post-order traversal of the same Node tree. I don't know if I'd call this class a BinarySearchTree though. Probably more appropriate to call it a TreeTraverser.

There's actually an extra level of BinarySearchTree than there are levels in your Node tree. Each leaf on the Node tree will get two BinarySearchTrees with null roots:

 
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just a question, Inorder traversal of the binary tree results complexity o(n) also the traversal is equivalent to the Linked list. So why we can't use Linked List
specially for the in-order case as it is simple to implement then Binary Tree and results sample complexity?
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So, traversing the Node tree I gave above, you get the following results

Which line do you not understand here?
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, i mean i was reading an article about Binary Tree, it was mentioned that for random type of number, binary search tree gives very good performance.
Height of such tree becomes logN but if numbers are sorted then it gives the binary tree as an in-order i.e. the height becomes n. Which is equivalent to the
linked list. So i was thinking if we know then numbers are not random but sorted then could we use LinkedList as both same performance in specific to this
case?
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Tushar your question is on a tangent from the OPs so if you want to pursue it, please start another topic.

@Juna do you still have doubts about the flow?
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok. Sorry for confusion.. I will open a new thread for the same.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Juna, I think it will be less confusing if you make the following tweaks to your class:

this is the output from running this:

I modified the Node class so I could instantiate it with a name attribute, which is what is returned by its overridden toString() method.

Does this clarify the visiting and output sequence for you?
 
Juna Burk
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hey Junilu,

thanks a lot for your answer! Now everything is clear to me :-)

Best,
Juna
reply
    Bookmark Topic Watch Topic
  • New Topic