Question

26-ary tree for spell checker in JAVA
You are asked to write some functionalities for a spelling checker inside Tree.java that has at least the following methods:

  /*Adds a word to a spelling checker’s collection of correctly spelled words*/
  void add(String word)

  /*Returns true if the given word is spelled correctly*/
  boolean check(String word)

  /*Returns back all words in the tree in alphabetical order*/
  public String getDictionaryInAlphabeticalOrder()

Store the collection of correctly spelled words in a 26-ary tree. The number 26 indicates that each node in the tree has atmost 26 children (i.e. one each for the english alphabet). Each node in this tree has a child corresponding to a letter in the alphabet. Each node also indicates whether the word represented by the path between the root and the node is spelled correctly. For example, the tree shown in figure 1 depicts this indication as a filled-in node (in black color). This tree stores the words “boa,” “boar,” “boat,” “board,” “hi,” “hip,” “hit,” “hop,” “hot,” “trek,” and “tram.”

To check whether a given word is spelled correctly, you begin at the tree’s root and follow the reference associated with the first letter in the word. If the reference is null, the word is not in the tree. Otherwise, you follow the reference associated with the second letter in the word, and so on. If you finally arrive at a node, you check whether it indicates a correctly spelled word. For example, the tree in figure 1 indicates that “t,” “tr,” and “tre” are spelling mistakes, but “trek” is spelled correctly.

package;

public class Tree {

private Node root;

private class Node {

/*

* TODO: Complete the class Node.

* You can add any number of instance variables or methods

* or constructor to the Node class.

*/

}

/*

* We have completed the constructor of the Tree class.

*/

public Tree()

{

root=new Node();

}

/*

* TODO: add the word into the tree based on the structure

* provided in the handout. You must use recursion. Feel free

* to create a helper private method that will do the recursion

* for you.

*/

public void add(String word)

{

}

/*

* TODO: Checks whether the word is present in the tree or not.

* You must use recursion. Feel free

* to create a helper private method that will do the recursion

* for you.

*/

public boolean check(String word)

{

return false;

}

/*

* We have already completed this method for you.

* This method works with the preconditions that all letter

* are lower case and between and inclusive a-z

* For example, if the letter is a, then the output is 0

* For example, if the letter is b, then the output is 1

* For example, if the letter is c, then the output is 2

* .

* .

* .

* For example, if the letter is z, then the output is 25

*/

private static int convertFromLetterToIndexPosition(char letter)

{

int temp = (int)letter;

int temp_integer = 96; //for lower case

return (temp-temp_integer-1);

}

/*

* We have already completed this method for you.

* This method works with the preconditions that all integers

* are between 0 and 25.

* For example, if the index is 0, then the output is a

* For example, if the letter is 1, then the output is b

* For example, if the letter is 2, then the output is c

* .

* .

* .

* For example, if the letter is 25, then the output is z

*/

private static String convertFromIndexToLetter(int index)

{

return String.valueOf((char)(index + 97));

}

/*

* TODO: You must complete this method. You can use recursion or no recursion.

* It is completely up to you. This method however, must return back a string of

* words in alphabetical order that represents the dictionary that the tree is

* currently holding. See the main method for an expected output of this.

*/

public String getDictionaryInAlphabeticalOrder()

{

}

public static void main(String[] args)

{

Tree dictionary=new Tree();

dictionary.add("abbas");

dictionary.add("ab");

dictionary.add("a");

dictionary.add("xan");

dictionary.add("ban");

dictionary.add("acbbas");

dictionary.add("cat");

dictionary.add("dog");

System.out.println(dictionary.check("abbas")); //true

System.out.println(dictionary.check("ab")); //true

System.out.println(dictionary.check("abb")); //false

System.out.println(dictionary.check("a")); //true

System.out.println(dictionary.check("xab")); //false

System.out.println(dictionary.check("xan")); //true

System.out.println(dictionary.getDictionaryInAlphabeticalOrder()); //a ab abbas acbbas ban cat dog xan

}

}

Answer 1

package com.example;

import java.util.ArrayList;
import java.util.List;

public class Tree {

    private Node root;

    private class Node {
        Boolean isEnd;
        Node childNode[];
        public Node() {
            childNode = new Node[26];
            isEnd = Boolean.FALSE;
        }
    }

    /*

     * We have completed the constructor of the Tree class.

     */

    public Tree()

    {

        root=new Node();

    }

    /*

     * TODO: add the word into the tree based on the structure

     * provided in the handout. You must use recursion. Feel free

     * to create a helper private method that will do the recursion

     * for you.

     */

    public void add(String word) {
        Node current = this.root;
        addChar(word, 0, current);

    }

    // insert char from word recursively
    private void addChar(String word, int index, Node current) {
        if (index >= word.length()) {
            current.isEnd = Boolean.TRUE;
            return;
        }
        int indexValue = convertFromLetterToIndexPosition(word.charAt(index));
        if (current.childNode[indexValue] == null) {
            current.childNode[indexValue] = new Node();
        }
        current = current.childNode[indexValue];
        addChar(word, index + 1, current);
    }

    /*

     * TODO: Checks whether the word is present in the tree or not.

     * You must use recursion. Feel free

     * to create a helper private method that will do the recursion

     * for you.

     */

    public boolean check(String word)

    {
        return checkChar(word, 0, this.root);

    }

    // check if word exist recursively
    private boolean checkChar(String word, int index, Node current) {
        if (current == null) {
            return false;
        }
        if (index >= word.length()) {
            return current.isEnd;
        }
        int indexValue = convertFromLetterToIndexPosition(word.charAt(index));
        return current.childNode[indexValue] == null ? Boolean.FALSE :
                checkChar(word, index + 1, current.childNode[indexValue]);

    }

    /*

     * We have already completed this method for you.

     * This method works with the preconditions that all letter

     * are lower case and between and inclusive a-z

     * For example, if the letter is a, then the output is 0

     * For example, if the letter is b, then the output is 1

     * For example, if the letter is c, then the output is 2

     * .

     * .

     * .

     * For example, if the letter is z, then the output is 25

     */

    private static int convertFromLetterToIndexPosition(char letter)

    {

        int temp = (int)letter;

        int temp_integer = 96; //for lower case

        return (temp-temp_integer-1);

    }

    /*

     * We have already completed this method for you.

     * This method works with the preconditions that all integers

     * are between 0 and 25.

     * For example, if the index is 0, then the output is a

     * For example, if the letter is 1, then the output is b

     * For example, if the letter is 2, then the output is c

     * .

     * .

     * .

     * For example, if the letter is 25, then the output is z

     */

    private static String convertFromIndexToLetter(int index)

    {

        return String.valueOf((char)(index + 97));

    }

    /*

     * TODO: You must complete this method. You can use recursion or no recursion.

     * It is completely up to you. This method however, must return back a string of

     * words in alphabetical order that represents the dictionary that the tree is

     * currently holding. See the main method for an expected output of this.

     */

    public String getDictionaryInAlphabeticalOrder() {
        List<String> stringList = new ArrayList<>();
        getDictionary(this.root, "", stringList);
        String str = "";
        for (String s : stringList) {
            str += s + " ";
        }
        return str;
    }

    // Recursively get dictionary words

    private void getDictionary(Node current, String str, List<String> masterStr) {
        if (current.isEnd) {
            masterStr.add(str);
        }
        for (int i = 0; i < current.childNode.length; i++) {
            if (current.childNode[i] != null) {
                String newStr = str + convertFromIndexToLetter(i);
                getDictionary(current.childNode[i], newStr, masterStr);
            }
        }
    }

    public static void main(String[] args)

    {

        Tree dictionary=new Tree();

        dictionary.add("abbas");

        dictionary.add("ab");

        dictionary.add("a");

        dictionary.add("xan");

        dictionary.add("ban");

        dictionary.add("acbbas");

        dictionary.add("cat");

        dictionary.add("dog");

        System.out.println(dictionary.check("abbas")); //true

        System.out.println(dictionary.check("ab")); //true

        System.out.println(dictionary.check("abb")); //false

        System.out.println(dictionary.check("a")); //true

        System.out.println(dictionary.check("xab")); //false

        System.out.println(dictionary.check("xan")); //true

        System.out.println(dictionary.getDictionaryInAlphabeticalOrder()); //a ab abbas acbbas ban cat dog xan

    }

}