Java: Word and Prefix search using the Tries data structure.

I am assuming you know the basic details about tries.

The tries node contains a character map and a flag indicating whether this is the end of a word or not.

Representation of tries node

Let’s insert “medium” in tries

Diagram of nodes connected to each other in tries

How it looks after the insertion.

Inserting “med” into tries

Diagram after insertion of med.

Inserting “muk” into tries now

Diagram after insertion.

The rest of the node is connected to d due to the large image skipping this.
In-depth, a tries node is a combination of a map of characters and a flag.

Tries Node depth representation

Case 1: Insertion in tries

Case 2: Deletion in tries

Case 3: Search Word or by prefix

Time and Space Complexity :

1. Insertion:
   Time: O(L * n)
   Space: O(alphabet_size * L* n)
2. Search :
   Time: O(L)
3. Deletion:
   Time: O(L * n)

Where L is avg length of the word and n is the total no of words.

Time and Space complexity always depends upon the best and worst cases.

Solution and test cases

problem-solving/TriesNode.java at 49e95f17875ecaf50dbe3a1285a90b1f609de47f ·…

problem-solving/WordSearch.java at 3132dc26666642d0d593cae8167bd86c0fd7504e ·…

If you are curious
https://www.youtube.com/watch?v=NinWEPPrkDQ

Happy Learning !!! Hope you like it.