views:

97

answers:

1

This is a past exam paper on binary search trees I am attempting. I have no way to check if the output is correct as I am not capable of building one of these things.

The question is in the title

class Tree{
    Tree left;
    Tree right;
    int key;

   public static int span(Tree tree)
   {
        if ( tree == null ){
             return null;
        }

        if( tree.left != null)
             int min = span(tree.left);
         }

        if( tree.right != null){
             int max = span(tree.right);
         }
         return max - min;
    }
}

Could anyone suggest what I need to change to get 5/5 marks :D - the only thing we have to do is write the span method, the header was given for us.

+1  A: 

You need to define two methods, min(Tree) and max(Tree), then span(Tree t) is defined as max(t) - min(t). span itself shouldn't be recursive, but you can make min and max recursive if you want.

Note that min and max doesn't have to be their own methods. If you don't care for making them stand as their own units, you can put it all into span like this:

int span(Tree t) {
   Tree tMin = t;
   while (tMin.left != null) {
      tMin = tMin.left;
   }

   Tree tMax = t;
   while (tMax.right != null) {
      tMax = tMax.right;
   }

   return tMax.key - tMin.key;
}
polygenelubricants
i think this is the best approach as its an algorithms module, they may frown upon using library methods, would it be possible to do this in one method? they only gave the span method as standard, i cant see there being an issue with making more methods but wouldnt like to chance it if possible
stan
You can do it in one method recursive method, but you have to save the actual subtraction to the point at which you have figured out the min of the whole tree, and max of the whole tree. See my edited answer abover.
aioobe
@stan, so the definition of "lowest" and "highest" keys are the "left-most" and "right-most" keys??
aioobe
yes thats right
stan
i have just noticed, wouldnt the way the above has been coded modify the original tree as Tree tMin = t just acts as a pointer to t rather than a copy, So you can't just do tMax = t to get to the top as the original tree will have been modified
stan
@stan: the tree is not modified at all. It's merely traversed. You can just use getters (if that's what's provided); you don't need setters.
polygenelubricants
@aioobe: The tags of the question includes `[binary] [search] [tree]`; I've encouraged OP to **explicitly** state this in the text also.
polygenelubricants
Ah. good point.
aioobe
ok then, the above way makes a lot of sence tbh - very clearly written and easy to follow, thanls for taking the time to help
stan
i have editied the original text also
stan