Given a node structure for compact trie:

Node $\{$

String label;

Node rightSibling; Node firstChild; bool isWord;

$\}$

Write a code for prefix searching a string in this trie. Node PrefixSearch$($Node root, String prefix$)$ will return a node which maximally matches.

b$)$ Now extend the above code to output all the words which match the query prefix.

$1$

c$)$ Further, we can these node pointers and lists $-$ and just use hashtable to do parent child navigation:

class TrieNode $\{$ String label;

bool isWord; $\}$

And a hashtable which maps a h:$($node$,$ char$)->$ node. Thus, to find a child node of a current node which has a particular beginning character 'char' we use this hashtable. This allows us to jump from parent to child considering appropriate branch character.

Assuming that the Trie and HashTable are already built. Show how to change Node PrefixSearch$($Node root, String prefix$)$ to use hashtable.

Like in the earlier subpart, let's say the query string prefix ends up in an in between node. Is it easy to find out all the words which match this prefix?