javastringbinary-search-treeletters

Binary Search Tree searching a string by letter


Hi I am a novice programmer trying to figure out how to search for a string in a binary search tree using only the first letter it starts with, for example if a just search for the letter 'L' it should bring up all names starting with that letter. Below is the method on how we search for the full name so far.

public void searchByName() throws IOException//My pride and joy
    {

        String exit=null;//to exit the inner while loop
        Boolean end=false;// exit the outer while loop

        while(end!=true) //search author by first name loop 
        {


            @SuppressWarnings("resource")
            Scanner keyboard = new Scanner(System.in);

            System.out.printf("Please enter the Author's Last and First:(please enter in this format(Johnson, Cevion)\n");
                String name = keyboard.nextLine();

                System.out.println("This is what we found!!\n");

                System.out.println(findFullName(name));


                System.out.printf("Do you want to search again?? Yes or No\n");//search again loop
                exit = keyboard.nextLine();


                while(!exit.equalsIgnoreCase("yes")&&!exit.equalsIgnoreCase("no"))//yes or no only loop
                {
                    System.out.printf("Invaild choice please enter: Yes or No\n");
                    exit = keyboard.nextLine();
                }

                if(exit.equalsIgnoreCase("yes"))
                    end=false;
                if(exit.equalsIgnoreCase("no"))
                    end=true;
        }

    }

Solution

  • Binary tries aren't meant for that kind of search, you better use a hashmap: string -> array

    if you would like to implement that kind of behaviour in a tree you will need to modify (or create) the search method, once it found the first node that match the criteria, in your case string starts with "L", it need to return that node and traverse the tree originate form that node, you can do it with a simple in-out order traverse and etc... and check all subsequent nodes for that criteria, it can't stop till got to the leaf thus makes this find complexity as O(N) basically traverse all the (sub)tree..