Binary tree using Strings and having issues adding a node

Question

I need to create a binary tree for my Java data structures class. I am still fairly new, so please excuse any rookie mistakes. My Btree needs to contain nodes of type String. My problem is that I can add one name, but when I go to add a second name, my program crashes and I get the following error.

Exception in thread "main" java.lang.StackOverflowError
at java.lang.Character.toUpperCase(Unknown Source)
at java.lang.Character.toUpperCase(Unknown Source)
at java.lang.String$CaseInsensitiveComparator.compare(Unknown Source)
at java.lang.String$CaseInsensitiveComparator.compare(Unknown Source)
at java.lang.String.compareToIgnoreCase(Unknown Source)

Here is my code:

BTNode

public class BTNode {

private String word;
private BTNode rPoint, lPoint;

public BTNode(String pWord){
    word = pWord;
    rPoint = null;
    lPoint = null;
}

public void setWord(String pWord){
    word = pWord;
}

public String getWord(){
    return word;
}

public void setRight(BTNode pRight){
    rPoint = pRight;
}

public BTNode getRight(){
    return rPoint;
}

public void setLeft(BTNode pLeft){
    lPoint = pLeft;
}

public BTNode getLeft(){
    return lPoint;
    }
}

BTree

public class BTree {

private BTNode root;

    public void setRoot(BTNode pRoot){
        root = pRoot;
    }

    public BTNode getRoot(){
        return root;
    }

    public BTNode addOne(BTNode pRoot, String pName){
        if(pRoot == null){
            BTNode temp = new BTNode(pName);
            pRoot = temp;
            temp.setWord(pName);
        }else if(pName.compareToIgnoreCase(pRoot.getWord()) > 0){
            pRoot.setLeft(addOne(pRoot, pName));
        }else if(pName.compareToIgnoreCase(root.getWord()) < 0){
            pRoot.setRight(addOne(pRoot, pName));
        }
        return pRoot;
    }

    public void displayAll(BTNode current){
        if(current != null){
            displayAll(current.getLeft());
            System.out.println(current.getWord());
            displayAll(current.getRight());
        }
    }

    public BTNode BTSearch(BTNode pRoot, String pName){
        BTNode found = null;
        if(pRoot == null){
            found = null;
        }else{
            if(pName.equalsIgnoreCase(pRoot.getWord())){
                found = pRoot;
            }
            else if(pName.compareToIgnoreCase(root.getWord()) < 0){
                found = BTSearch(root.getLeft(), pName);
            }else{
                found = BTSearch(root.getRight(), pName);
            }
        }return found;
    }
}

BTreeUser

import java.util.Scanner;

public class BTreeUser {

public static void main(String []args){

    int select = 0;
    BTree tree = new BTree();

    do{
        dispMenu();
        select = getSelection();
        proChoice(select, tree);
    }while(select != 0);

}


    public static void dispMenu(){
        System.out.println("\n|*******************************|");
        System.out.println("|-------------------------------|");
        System.out.println("|************Welcome************|");
        System.out.println("|                               |");
        System.out.println("|  Press [1] to add an entry    |");
        System.out.println("|                               |");
        System.out.println("|  Press [2]|to search          |");
        System.out.println("|                               |");
        System.out.println("|  Press [3] to display all     |");
        System.out.println("|                               |");
        System.out.println("|  Press [0] to exit            |");
        System.out.println("|                               |");
        System.out.println("|Make selection and press[ENTER]|");
        System.out.println("|-------------------------------|");
        System.out.println("|*******************************|\n");
    }

    public static int getSelection(){
        Scanner input = new Scanner(System.in);
        int selection = input.nextInt();
        return selection;
    }

    public static String inputWord(int select){
        Scanner input = new Scanner(System.in);
        String lName = null;
        if(select == 1){
        System.out.println("Please input word now: ");
        lName = input.nextLine();
    }else if(select == 2){
        System.out.println("Please input word to search for now: ");
        lName = input.nextLine();

        }
        return lName;
    }

    public static  void proChoice(int select, BTree tree){
        String pName;
        switch(select){
        case 1: pName = inputWord(select);
                tree.setRoot(tree.addOne(tree.getRoot(), pName));
                break;
        case 2: pName = inputWord(select);
                tree.BTSearch(tree.getRoot(), pName);
                break;
        case 3: tree.displayAll(tree.getRoot());
                break;
        case 0: System.out.println("Thank you, come again...");
                break;
        }

    }
}

I know the error is occurring in my addOne method is BTree. I am not sure if I am using compareToIgnoreCase correctly. Please, any help or suggestions as to how I can fix this or any changes I need to make would be greatly appreciated.

janos · Accepted Answer · 2015-10-17 06:20:17Z

1

The method calls itself with exactly the same parameters that it received:

 pRoot.setLeft(addOne(pRoot, pName));

As nothing changes in the input, nothing can ever change, the recursion is infinite.

The fix:

pRoot.setLeft(addOne(pRoot.getLeft(), pName));

The same goes for the right branch.

answered Oct 17, 2015 at 6:20

janos

126k31 gold badges242 silver badges253 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Scruffy Nerfherder Over a year ago

Okay, I see! Thank you very much sir, that did the trick :) I totally missed that but I see my mistake.

Collectives™ on Stack Overflow

Binary tree using Strings and having issues adding a node

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related