• Post Reply Bookmark Topic Watch Topic
  • New Topic

Subtree method in polymorphic BST  RSS feed

 
Adam Watson
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, not sure if this is the right place for this but I could really use some help. I have to write a method that takes two keys and returns a tree with only the keys between the two passed. The tree is a polymorphic binary search tree (aka one that uses an EmptyTree object instead of null to represent empty) that consists of a key and a value, along with a left and right tree containing the rest of the tree. The tree is also already sorted. Oh, and it has to be done recursively.
The method signature looks like this:

public Tree<K, V> subTree(K fromKey, K toKey)

All other methods of the Tree interface have been implemented and are working but I just can't seem to figure this one out.
Any help would be VERY greatly appreciated.
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

You need some sophisticated technology: pencil paper and eraser. The latter is by far the most important

Write down exactly what you intend to do. Get it down to words of one syllable. For an example, this is how you can implement recursion
Do the same for the left branch of the tree from this place
. . .
And at this point you can do the same for the right branch of the tree
Once you have finished that, you will have pseudo-code which you can easily convert to code.

As you doubtless know, most of these trees do their sorting as the elements are inserted. to find whether you have an empty tree you can try the instanceof operator, but that will be unreliable if your empty class is a super class of a "full" tree class. you might end up testingor something similar.
 
Adam Watson
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, thanks for the reply. I understand how to use recursion, just not how to apply it in this case. Also, I can't use the instanceof operator for this method. While I was trying to write the method I came up with this base case

But then I don't know where to go from there. I'm not sure what I need to do at each node. And another thing I forgot to mention is that the method cannot modify the current object. It has to return a new NonEmptyTree, the constructor for which takes a key, a value, and a left and right tree.
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Look at the local value. Assuming the lesser values go on the left, if the local value is greater than your search key, recurse to the left. If the local value is less than your search key, recurse to the right. Only return this if the two values are the same. You can probably do it with a set of if-elsesIf you have an EmptyTree class, you can return that when there is no value on one of the leaves.

It seems an unusual tree having special classes rather than nulls to mark its leaves.
 
Adam Watson
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ha, I got it! I used the if-else structure you suggested and returned a new nonemptytree in the else, passing it the key and value of the current node, but for the left and right trees, I called subtree on them so it would return the subtree of the left and right trees. Thank you so much for your help. Very glad I signed up for this and will most likely use it again when I'm stuck lol.
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well done

An thank you for giving a solution in case anybody else has a similar problem in future.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!