Binary Search Tree Iterate non-keys

Question

I have a bit of a conundrum. I need to print all the values in my BST that are NOT keys. So since the tree is not ordered according to these values, I can't do as I normally have with BSTs in the past. I simply need to look at EVERY node on the tree, compare the non-key value with the value I have entered, and determine whether to print it.

I.E. Student directory where I need to print all GPAs above a 2.0. Since the tree is ordered by Student IDs and not GPA, how do I go through every node and compare GPA and print all nodes that are above 2.0?

If you need to look at my code, the whole thing is here, and it's enormous.

public class StudentBST
{
private static Node root;

static class Node
{
    public int studentID;
    public String lastName;
    public String firstName;
    public String major;
    public double gpa;
    public Node left, right;

    public int minValue()
    {
        if(left == null)
        {
            return studentID;
        }
        else
        {
            return left.minValue();
        }
    }

    public boolean remove(int i, Node node)
    {
        if(i < this.studentID)
        {
            if(left != null)
            {
                return left.remove(i, this);
            }
            else
            {
                return false;
            }
        }
        else if(i > this.studentID)
        {
            if(right != null)
            {
                return right.remove(i, this);
            }
            else
            {
                return false;
            }
        }
        else
        {
            if(left != null && right != null)
            {
                this.studentID = right.minValue();
                right.remove(this.studentID, this);
            }
            else if(node.left == this)
            {
                node.left = (left != null) ? left : right;
            }
            else if(node.right == this)
            {
                node.right = (left != null) ? left : right;
            }
            return true;
        }
    }

    public Node(int i, String l, String f, String m, double g)
    {
    studentID = i;
    lastName = l;
    firstName = f;
    major = m;
    gpa = g;
    left = null;
    right = null;
    }
}
public StudentBST()
{
    root = null;
}
private static void insert(int i, String l, String f, String m, double g)
{
    root = insert(root, i, l, f, m , g);
}
private static Node insert(Node node, int i, String l, String f, String m, double g)
{
    if(node == null)
    {
        node = new Node(i, l, f, m, g);
    }
    else
    {
        if(i <= node.studentID)
        {
            node.left = insert(node.left, i, l, f, m, g);
        }
        else
        {
            node.right = insert(node.right, i, l, f, m, g);
        }
    }
    return(node);
}
public static void printBST()
{
    printBST(root);
    System.out.println();
}
private static void printBST(Node node)
{
    if(node == null)
    {
        return;
    }
    printBST(node.left);
    System.out.println(node.studentID + ", " + node.lastName + ", " + node.firstName
    + ", " + node.major + ", " + node.gpa);
    printBST(node.right);
}
public static boolean remove(int i)
{
    if(root == null)
    {
        return false;
    }
    else
    {
        if(root.studentID == i)
        {
            Node auxRoot = new Node(0, "", "", "", 0);
            auxRoot.left = root;
            boolean result = root.remove(i, auxRoot);
            root = auxRoot.left;
            return result;
        }
        else
        {
            return root.remove(i, null);
        }
    }
}
public static void main(String[] args) 
{
    StudentBST.insert(8, "Costanza", "George", "Napping", 1.60);
    StudentBST.insert(10, "Kramer", "Cosmo", "Chemistry", 3.04);
    StudentBST.insert(5, "Seinfeld", "Jerry", "Theater", 2.05);

    StudentBST.printBST();
    Scanner input = new Scanner(System.in);
    int option = 9;

    while(option != 0)
    {
        System.out.println("1 - Add new student 2 - Delete student 3 - Print All" + 
                " 0 - Exit");
        option = input.nextInt();

        if(option == 1)
        {
            System.out.println("Enter student ID");
            int i = input.nextInt();
            input.nextLine();

            System.out.println("Enter Last Name");
            String l = input.nextLine();

            System.out.println("Enter First Name");
            String f = input.nextLine();

            System.out.println("Enter major");
            String m = input.nextLine();

            System.out.println("Enter GPA");
            Double g = input.nextDouble();

            System.out.println("Inserted student record");
            StudentBST.insert(i, l, f, m, g);
        }
        if(option == 2)
        {
            System.out.println("Enter Student ID to delete");
            int i = input.nextInt();
            boolean b = StudentBST.remove(i);
            if(b)
            {
                System.out.println("Deletion completed");
            }
            else
            {
                System.out.println("Deletion encountered error");
            }
        }
        if(option == 3)
        {
            StudentBST.printBST();
        }
    }
}

Answer 1

I think you have the right idea: just walk across the whole tree and print out GPAs higher than a certain threshold. A rough implementation looks like:

public void printGPAs(Node node, double gpa_cutoff) {
    if (node == null) {
        return;
    } 

    if (node.gpa >= gpa_cutoff) {
        System.out.println(node.gpa);
    }

    printGPAs(node.left);
    printGPAs(node.right);
}

If you wanted to print them out in a particular order, the easiest way would be to drop them in to a list as you go along, inserting in the correct place to maintain your desired order.