Adam Watson

Greenhorn

Posts: 3

posted 7 years ago

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.

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

posted 7 years ago

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

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.

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

Once you have finished that, you will have pseudo-code which you can easily convert to code.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

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

posted 7 years ago

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.

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

posted 7 years ago

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

It seems an unusual tree having special classes rather than

`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

`null`s to mark its leaves.
Adam Watson

Greenhorn

Posts: 3

posted 7 years ago

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.