Scientific Programming II

Programming in Java

Trees Quiz

Problem 1 (10 Points)

Write a method to print the maximum prime number in a binary search tree. If there are no prime numbers in the binary search tree, the method should return Integer.MAX_VALUE or Integer.MIN_VALUE

The basic algorithm for this problem is as follows:

func getMaxPrime(node)

    maxPrimeLeft <- getMaxPrime(leftSubTree)
    maxPrimeRight <- getMaxPrime(rightSubTree)

    maxPrime <- max(node, max(maxPrimeLeft, maxPrimeRight))

    return maxPrime

endfunc

Note: In psuedocode, <- means assignment and = means equality

Extend this pseudocode algorithm into a method public int getMaxPrime() in Tree.java that finds the maximum prime number stored in the tree. Note that you will need to account for missing children, and the primality of each number, as the pseudocode does not. Additionally, using the techniques from the recursion tutorial will help you immensely.

Helpful Hints

Hint 1

Math.max(int a, int b) will return the maximum of two integers.

Hint 2

public boolean isPrime(int p)
{
    int i = 2;
    boolean m = true;

    if (p == 1 || p == 0) {
        return false;
    } else { 
        while (i < p && m == true) {
            if (p % i == 0)
                m = false;
            else
                i++;
        }
    }

    return m;
}