Trie Data Structure and implementation to insert,search, count, delete words from trie

By The Glitcher | The Glitcher | 14 Jan 2022

Trie is a tree data structure which is used widely in google autocomplete, spell checker and prefix matching for ip routing in IP tables. It is also a very efficient data structure compared to hashtable in terms of storing and searching the strings based on prefix.

For example,

Storing strings - "apple", "app", "apps" in a hash table takes 12 character storage.

apple -> 5

app -> 3

apps -> 4

But in trie it can be stored as a tree, like

a -> p -> p -> l -> e

-> s

A total of only 6 characters space. As app is already present in apple, we don't create extra space for it.

A detailed implementation of how to implement a trie in Java is mentioned here in this blog.

AutoComplete Use case

Lets take another example of inserting similar words search as bag, bat, bar, ball, bard, batsman, batter, bald

In Trie, it would be stored like

b->a->t (bat)

->s->m->a->n(batsman)

->t->e->r(batter)

->g(bag)

->r(bar)

->l->l(ball)

->d(bald)

->r->d(bard)

When we search a prefix like ba in google, it searches for all the words with prefix ba and recommends the suggestions in terms of autocomplete like

bard,ball, bat, batsman.

Spell Checker Usecase

This works similar to autocomplete however, it will try to find the word upto a given prefix in the trie. If the word is not found in the trie, it will return the words with the prefix words available in the trie.

For example, If we search ban but it available in try, the longest prefix it matches for ban word is ba. So it returns the words with prefix ba to correct the ban word to a word available in trie.