Return the difference between the smallest and highest key - Binary Search Tree

Question

This is the last binary search tree exam paper I am trying to do. I have no way to verify the correctness of the conclusion, since I cannot create 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; } } 

Can anyone suggest that I need to change to get 5/5 tags: D is the only thing we need to do is write the span method, the title was given for us.

Answer 1

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

Note that min and max should not be their own methods. If you do not want them to stand as their own units, you can put it all in a span as follows:

 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; }