Why are the Trie Functions unable to produce my desired output?

Question

Your task is to create a trie system that is hosted online with a global state that supports multiple concurrent clients and the following operations:

1. Add keyword to trie
2. Delete a keyword from trie
3. Search for a keyword in trie [True/False]
4. Return list of autocomplete suggestion based on an input prefix
5. Display the trie

Node Class:

package com.stack.trie;

public class Node {
    public Node[] links = new Node[26];
    public int ctrEndWith;
    public int ctrPrefix;
    public boolean flag;

        boolean containsKey(char ch)
        {
            return (links[ch-'a']!=null);
        }

        Node get(char ch)
        {
            return links[ch-'a'];
        }

        void put(char ch,Node node)
        {
            links[ch-'a']=node;
        }

        void increaseEnd()
        {
            ctrEndWith++;
        }

        void increasePrefix()
        {
            ctrPrefix++;
        }

        void deleteEnd()
        {
            ctrEndWith--;
        }

        void reducePrefix()
        {
            ctrPrefix--;
        }

        int getEnd()
        {
            return ctrEndWith;
        }

        int getPrefix()
        {
            return ctrPrefix;
        }

        void setEnd()
        {
            flag=true;
        }

        boolean isEnd()
        {
            return flag;
        }
}    

And Functions:

public class Trie1 {
    public Node root = new Node();

    public void add(String word) {
        Node node = root;
        int i;
        for (i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node.put(word.charAt(i), new Node());
            }
            node = node.get(word.charAt(i));
            node.increasePrefix();
        }
        node.setEnd();
    }

    public boolean search(String word) {
        Node node = root;
        int i;
        for (i = 0; i < word.length(); i++) {
            if (!node.containsKey(word.charAt(i))) {
                return false;
            }
            node = node.get(word.charAt(i));
        }
        return node.isEnd();
    }

    void delete(String word) {
        Node node = root;
        int i;
        for (i = 0; i < word.length(); i++) {
            if (node.containsKey(word.charAt(i))) {
                node = node.get(word.charAt(i));
                node.reducePrefix();
            } else {
                return;
            }
        }
        node.deleteEnd();
    }

    void suggest() {

    }

    String display() {
        return null;
    }

    public void mainMenu() {
        Scanner sc = new Scanner(System.in);
        int ch;
        String str;
        do {
            System.out.println("\t\tTrie Menu");
            System.out.println("\t\t1.Add");
            System.out.println("\t\t2.Delete");
            System.out.println("\t\t3.Search");
            System.out.println("\t\t4.Return Suggestions");
            System.out.println("\t\t5.Display Trie");
            System.out.println("\t\t6.Exit");
            System.out.print("\t\tPlease enter a choice.");
            ch = sc.nextInt();

            switch (ch) {
                case 1:
                    System.out.println("Enter keyword to be added");
                    str = sc.nextLine();
                    add(str);
                    break;
                case 2:
                    System.out.println("Enter keyword to be deleted");
                    str = sc.nextLine();
                    break;
                case 3:
                    System.out.println("Please enter search term");
                    str = sc.nextLine();
                    search(str);
                    break;
                case 4:
                    System.out.println("Please enter prefix");
                    str = sc.nextLine();
                    break;
                case 5:
                    display();
                    break;
                case 6:
                    System.out.println("Thank you!");
                    break;
                default:
                    System.out.println("Invalid Input. Please try again.");
            }
        } while (ch != 6);
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        Trie1 obj = new Trie1();
        obj.mainMenu();
    }
}

Answer 1

On a first scan over your code already I identified two problems.

First problem:

In mainMenu() you use sc.nextInt() to read the menu selection. After that you use sc.nextLine() (for example to read the keyword to be added). This is problematic because sc.nextInt() did not consume the line terminator after the int and therefore you always get an empty string for the keyword.

See Scanner is skipping nextLine() after using next() or nextFoo()? for more information.

In mainMenu() replace

ch = sc.nextInt();

with

ch = sc.nextInt();
sc.nextLine();

---

Second problem:

In the Trie1.add() method you add a new Node object to the current node only if it already contains a node:

        if (node.containsKey(word.charAt(i))) {
            node.put(word.charAt(i), new Node());
        }

You need to reverse the condition in the if statement:

        if (!node.containsKey(word.charAt(i))) {
            node.put(word.charAt(i), new Node());
        }

---

Also, why does your main method contain the line

Scanner sc = new Scanner(System.in);

You never use that sc so delete that unnecessary line.