• Post Reply Bookmark Topic Watch Topic
  • New Topic

contains method in 2D BST not working properly  RSS feed

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Greetings everyone,

I have a contains method in a 2D BST and it does not seem to be able to find all elements that are added to it. My approach is that I attempt to traverse the tree and return true if the item is found. However, it's not happening here. Here is my code thus far (entire project).



Where am I going wrong with my contains method? Thanks!
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One other thing that i forgot to mention is that my add method does not seem to be adding nodes in Level-Order Traversal. Where am I going wrong in my algorithm? Thanks!
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My suggestion would be to add some logging statements through the code so it can tell you what it is doing, and which branches it is going down.




That should help you find your logic error pretty quickly :-)
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please start by deciding how your tree will define containing and not containing. It is usually predicated on something like:-
myComparator.compare(instanceSought instanceFound) == 0
so you probably want to make sure the Comparator (or compareTo() method) being consistent with equals, as described in the TreeSet documentation..
Your method for contains looks very complicated, particularly to somebody as suspicious as me: I assume anything looking complicated is wrong even when it isn't. Remembering the definition of contains and doesn't contain, which you have already worked out, each node will have a value, a left branch, and a right branch. Depending on what happens when you compare your object to the value in the current node, you want to look at the value or to the left or to the right. At this point, I start thinking in terms of recursion, which will give you a method containing a single statement.
Avoid
if (myBooleanExpression) return true; else return false;
Go to the old Sun style guide and you will find you shou‍ld write
return myBooleanExpression;http://www.oracle.com/technetwork/java/javase/documentation/codeconventions-137265.html#333
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!