Homework help: Array being weird

Question

I'm working on a Binary Search Tree assignment, and I was testing what I thought was the finished product when I saw that when I added a number to the tree and then tried to check it's predecessor/successor (by putting it into an array using in order traverse and then checking the index before/after it) it just...didn't work. Any time I try to check the predecessor/successor of a value I just put in the middle of the tree, it wigs out with an ArrayIndexOutOfBoundsException. Important note is that simply printing out using inordertraverse (called printInOrder in the code) works perfectly.

Since printing the inorder traverse works, I can assume my tree isn't the problem. The only other thing is the array, right? Am I missing something obvious?

Here's the code!

public class BST implements BSTInterface
{
//Variables/Fields
    private BNode root;

//Constructors
    public BST(int data)
    {
        root = new BNode(data);
    }

//Public Methods
    public boolean add(int data)
    {
        if(!contains(data))
        {
            root = addEntry(root, data);
            return true;
        }
        else
            return false;
    }

    public boolean contains(int data)
    {
        return containsNode(root, data);
    }

    public boolean remove(int data)
    {
        if(contains(data))
        {
            root = deleteNode(root, data);
            return true;
        }
        else
            return false;
    }

    public int[] toArray()
    {
        int[] output = new int[root.numNodes()];
        inorderTraverse(output, 0, root);
        return output;
    }

    public void printInOrder()
    {
        printIn(root);
    }

    public void printPreOrder()
    {
        printPre(root);
    }

    public void printPostOrder()
    {
        printPost(root);
    }


//Private methods/classes
    private class BNode
    {
        private int data;
        private BNode leftChild;
        private BNode rightChild;

        public BNode(int data)
        {
            this.data = data;
            leftChild = null;
            rightChild = null;
        }

        public int getData()
        {
            return data;
        }

        public void setData(int newData)
        {
            data = newData;
        }

        public BNode getLeftChild()
        {
            return leftChild;
        }

        public BNode getRightChild()
        {
            return rightChild;
        }

        public void setRightChild(BNode node)
        {
            rightChild = node;
        }

        public void setLeftChild(BNode node)
        {
            leftChild = node;
        }

        public int numNodes()
        {
            int leftNum = 0;
            int rightNum = 0;

            if(leftChild != null)
                leftNum = leftChild.numNodes();
            if(rightChild != null)
                rightNum = rightChild.numNodes();

            return 1+leftNum+rightNum;
        }


    }

    private BNode addEntry(BNode current, int data)
    {
        if(current == null)
            return new BNode(data);
        if(data < current.getData())
            current.setLeftChild(addEntry(current.getLeftChild(), data));
        else if(data > current.getData())
            current.setRightChild(addEntry(current.getRightChild(), data));
        return current;
    }

    private boolean containsNode(BNode current, int entry)
    {
        if(current == null)
            return false;
        if(entry == current.getData())
            return true;
        if(entry < current.getData())
            return containsNode(current.getLeftChild(), entry);
        else
            return containsNode(current.getRightChild(), entry);

    }

    private BNode deleteNode(BNode current, int data)
    {
        if(current == null)
            return null;
        if(data == current.getData())
        {
            if(current.getLeftChild() == null && current.getRightChild() == null) //No children
                return null;
            if(current.getRightChild() == null) //Only right child
                return current.getLeftChild();
            if(current.getLeftChild() == null) //Only left child
                return current.getRightChild();
            int smallestChild = findSmallest(current.getRightChild());
            current.setData(smallestChild);
            current.setRightChild(deleteNode(current.getRightChild(), smallestChild));
            return current;
        }
        if(data < current.getData())
        {
            current.setLeftChild(deleteNode(current.getLeftChild(), data));
            return current;
        }
        else
            current.setRightChild(deleteNode(current.getRightChild(), data));
            return current;

    }

    private int findSmallest(BNode root)
    {
        return root.getLeftChild() == null ? root.getData() : findSmallest(root.getLeftChild());
    }

    private void inorderTraverse(int[] array, int count, BNode node)
    {
        if(node != null)
        {
            inorderTraverse(array, count, node.getLeftChild());
            array[count] = node.getData();
            count++;
            inorderTraverse(array, count, node.getRightChild());
        }
    }

    private void printIn(BNode node)
    {
        if(node != null)
        {
            printIn(node.getLeftChild());
            System.out.print(node.getData() + " ");
            printIn(node.getRightChild());
        }
    }

    private void printPre(BNode node)
    {
        if(node != null)
        {
            System.out.print(node.getData() + " ");
            printPre(node.getLeftChild());
            printPre(node.getRightChild());
        }
    }

    private void printPost(BNode node)
    {
        if(node != null)
        {
            printPost(node.getLeftChild());
            printPost(node.getRightChild());
            System.out.print(node.getData() + " ");
        }
    }
}

along with the driver program:

import java.util.Scanner;
public class BSTDemoReel
{
    public static void main(String[] args)
    {
        System.out.println("This search tree only handles integers! Thanks in advance!\n\n");
        Scanner keyboard = new Scanner(System.in);

        //Variables
        String input;
        String choice = "";
        int num;
        int index;
        boolean found;

        //Starting
        System.out.println("Please enter the initial sequence of values:\n");
        input = keyboard.nextLine();
        String[] splitInput = input.split(" ");
        int[] intInputArray = new int[splitInput.length];
        for(int count = 0; count < splitInput.length; count++)
        {
            intInputArray[count] = Integer.parseInt(splitInput[count]);
        }

        BST searchTree = new BST(intInputArray[0]);
        for(int count = 1; count < intInputArray.length; count++)
        {
            searchTree.add(intInputArray[count]);
        }

        System.out.print("Pre-order: ");
        searchTree.printPreOrder();
        System.out.println();

        System.out.print("In-order: ");
        searchTree.printInOrder();
        System.out.println();

        System.out.print("Post-order: ");
        searchTree.printPostOrder();
        System.out.println();

        //Menu
        while(!choice.equals("E"))
        {
            System.out.print("Command? ");
            choice = keyboard.next();
            choice = choice.toUpperCase();
            switch(choice)
            {
            case "I": num = keyboard.nextInt();
                    if(searchTree.contains(num))
                        System.out.println(num + " already exists. Please try again.");
                    else
                    {
                        searchTree.add(num);
                        System.out.print("In-order: ");
                        searchTree.printInOrder();
                        System.out.println();
                    }
                    break;
            case "D": num = keyboard.nextInt();
                    if(!searchTree.contains(num))
                        System.out.println(num + " does not exist. Please try again.");
                    else
                    {
                        searchTree.remove(num);
                        System.out.print("In-order: ");
                        searchTree.printInOrder();
                        System.out.println();
                    }
                    break;
            case "P": num = keyboard.nextInt();
                    if(searchTree.contains(num))
                    {
                        int[] array = searchTree.toArray();
                        index = 0;
                        found = false;
                        while(!found)
                        {
                            if(num == array[index])
                                found = true;
                            else
                                index++;
                        }
                        if(index != 0)
                            System.out.println(array[index-1]);
                        else
                            System.out.println("That was the first one!");
                    }
                    else
                        System.out.println(num + " does not exist! Please try again!");
                    break;
            case "S": num = keyboard.nextInt();
                   if(searchTree.contains(num))
                    {
                        int[] array = searchTree.toArray();
                        index = 0;
                        found = false;
                        while(!found)
                        {
                            if(num == array[index])
                                found = true;
                            else
                                index++;
                        }
                        if(index != array.length-1)
                            System.out.println(array[index+1]);
                        else
                            System.out.println("That was the last one!");
                    }
                    else
                        System.out.println(num + " does not exist! Please try again!");
                    break;
            case "E": System.out.println("Was a tricky one! Thanks for playing ;P");
                    break;
            case "H": System.out.println("I  Insert a value\n" +
                                         "D  Delete a value\n" +
                                         "P  Find predecessor\n" +
                                         "S  Find successor\n" +
                                         "E  Exit the program\n" +
                                         "H  Display this message");
                    break;

            default: System.out.println("Invalid command. Type H for help.");
                    break;
            }
        }
        keyboard.close();
    }
}

Answer 1

If you add a couple of lines of code to print out the array returned by searchTree.toArray() before you enter the while loop that examines the array to find the value specified with the P or S commands then you'll see the cause of the problem. The array is not filled in correctly. The desired value might not be present in the array, which means that found will never become True and the while loop will continue to increment index until it exceeds the size of the array and triggers the exception that you're seeing.

Since the array is supposed to be populated by inorderTraverse(), this suggests that that function isn't doing its job correctly. The reason why it is misbehaving is that its inner recursive calls to itself do not modify the value of the count variable for the caller. count is a simple int variable, therefore the count++ statement inside the recursive call does not affect the value of count in the calling function.

Your best options are either to change inorderTraverse() so that it returns the index of the array element that should be filled in next, or change count to be an Object that contains an int member whose updated value will be visible to the caller after it has been incremented inside the recursively called function.

Since this is an assignment I'm not going to show a corrected version of the program. The change is small, so given what you've done so far I expect that you won't have much trouble making it work.

BTW, your program is missing implementations of printIn(), printPre() and printPost(). They're not hard to write, but it's an extra hurdle for anyone who might have been interested in helping you tackle the problem. That might be at least part of the reason why no-one else has offered an answer yet. The easier you make it for people to reproduce the problem, the more likely it is that you'll get answers.