aspose file tools*
The moose likes Java in General and the fly likes Inorder traversal of a Binary Search Tree Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Inorder traversal of a Binary Search Tree" Watch "Inorder traversal of a Binary Search Tree" New topic
Author

Inorder traversal of a Binary Search Tree

Jim Hester
Ranch Hand

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 29, 2008
Posts: 12617

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

Joined: Sep 29, 2008
Posts: 12617

And why sometimes you use a getter/setter and sometimes access the property directly?
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

And always create a new bstNode? Never mind this one. Your code is kind of hard to read.
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

And call new String()?
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

Why are BstNode methods part of Main, instead of BstNode?
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

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

Joined: Sep 29, 2008
Posts: 12617

Is it true that a node's word "matters" only if left and right are null?
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

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

Joined: Sep 29, 2008
Posts: 12617

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

Joined: Sep 29, 2008
Posts: 12617

(And why isn't insert recursive?)
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

(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

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 19, 2009
Posts: 36
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

Joined: Sep 19, 2009
Posts: 36
Figured it out. Inorder looks like this now...

David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Inorder traversal of a Binary Search Tree