Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Inorder traversal of a Binary Search Tree

 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, I'm trying to do an inorder traversal of a binary search tree using recursion (doesn't HAVE to be recursion, but it seems the simplest to do. My "SizeOf" method works great, and I can print each node using that, so I know the tree is forming... Can anyone clue me into why my Inorder traversal isn't printing anything??

 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Would have been easier if you'd included the code for bstNode.

Is there a reason you break with Java convention and name all your methods starting with an upper case and at least one of your classes with a lower case, which is backwards?
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And why sometimes you use a getter/setter and sometimes access the property directly?
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And always create a new bstNode? Never mind this one. Your code is kind of hard to read.
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And call new String()?
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why are BstNode methods part of Main, instead of BstNode?
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What happens in inOrder if both left and right aren't null? And what happens to the strings those calls might return?
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is it true that a node's word "matters" only if left and right are null?
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If a BstNode has a word, is it ordered before, in the middle of, or after, that same node's left and right node's words?
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In any case, you're on the right track:

Yonder, and, and, appears, centuries, change, changeless, compassion, eternal, for, has, may, my, of, people, sky, tears, that, to, untold, upon, us, wept, which
I think I gave you a key hint, as well as a bunch of other commentary as played with the code here, paring it down to the minimal necessary to get it to work.
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(And why isn't insert recursive?)
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(It's also not clear to me that a node can actually ever be empty as per the test in inOrder(BstNode); a node's value is either set via insert right away if the node is empty, or via the BstNode ctor if adding a word to the right or left: I haven't written any unit tests for the refactoring I did, but is that the case?)
 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Been away for a few days, but working on this over the weekend. Code for bstNode attached.. Will attempt to answer questions below...

 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David Newton wrote:And call new String()?


yes? I'm still pretty new to programming in general and Java in particular. What's wrong with calling a new String()?
 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David Newton wrote:If a BstNode has a word, is it ordered before, in the middle of, or after, that same node's left and right node's words?


should be in the middle of. I've rewritten the code. will post here. it still doesn't do what I need it to do, though...
 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David Newton wrote:(And why isn't insert recursive?)


I tried to write it recursively, and it broke the program (or at least the SizeOf method). Now it consistently only counts 1 node... The good news is that it does print that node...
 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's what I have now. It still doesn't work, but it compiles fine.. Logically, I think it should work. Is there something simple that I'm not doing or doing wrong that's making it fail?


 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok, I partially figured out what was going wrong. I added some println each time a node was set and what I figured out is that it's usually just bypassing the comparisons and just incrementing frequencies... Which is odd, but at least a starting point...
The shuffled line:
dumpty horses couldn't the men put together king's and king's the All humpty all back again
Setting the as root: dumpty
incrementing the frequency of this node: horses
creating a left node from element: couldn't
incrementing the frequency of this node: the
incrementing the frequency of this node: men
incrementing the frequency of this node: put
incrementing the frequency of this node: together
incrementing the frequency of this node: king's
incrementing the frequency of this node: and
incrementing the frequency of this node: king's
incrementing the frequency of this node: the
incrementing the frequency of this node: All
incrementing the frequency of this node: humpty
incrementing the frequency of this node: all
incrementing the frequency of this node: back
incrementing the frequency of this node: again
counting: dumpty
counting: couldn't
The Size of the Tree is: 2
The Tree elements in order:
couldn't


Trying to debug now...
 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alright, so I changed the compareto from an "==" to a greater than/less than and it's filling the tree correctly. Still can't get the inorder traversal, however... Code as it looks now along with output:



The shuffled line:
and humpty king's the horses All all put dumpty king's the together couldn't again men back
Setting the as root: and
creating a right node from element: and
this word is going in the right node: humpty
creating a right node from element: humpty
this word is going in the right node: king's
creating a right node from element: king's
this word is going in the right node: the
creating a left node from element: humpty
this word is going in the left node: horses
creating a left node from element: and
this word is going in the left node: All
creating a right node from element: All
this word is going in the right node: all
creating a left node from element: the
this word is going in the left node: put
creating a left node from element: horses
this word is going in the left node: dumpty
incrementing the frequency of this node: king's
incrementing the frequency of this node: the
creating a right node from element: the
this word is going in the right node: together
creating a left node from element: dumpty
this word is going in the left node: couldn't
creating a left node from element: all
this word is going in the left node: again
creating a left node from element: put
this word is going in the left node: men
creating a left node from element: couldn't
this word is going in the left node: back
counting: and
counting: All
counting: all
counting: again
counting: humpty
counting: horses
counting: dumpty
counting: couldn't
counting: back
counting: king's
counting: the
counting: put
counting: men
counting: together
The Size of the Tree is: 14
The Tree elements in order:
again
 
Jim Hester
Ranch Hand
Posts: 36
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Figured it out. Inorder looks like this now...

 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Awesome!

(Although now it looks like Inorder doesn't need that string in there... and it's still named counter to Java convention :)

The reason you almost never need "new String()" is because it's shorter and cleaner to just say
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic