Instructions:

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.

Node PrefixSearch$($Node root, String prefix, String label$)\{$

Node current $=$ root;

int index $=0$;

while $($current $!=$ null && index $<$ prefix.length$())\{$

char c $=$ prefix.charAt$($index$)$;

$//$ if c is not in children nodes return false.. prefix does not exist in trie..

if $($current$.$label.charAt$(0)==$ null$)\{$

return null;

$\}$

$///$else shift current pointer to child pointer and continue searching

else $\{$

current $=$ current.firstChild$[$c$]$;

$\}$

$\}$

$//$Return current when we reach end of word meaning there is a prefix that exists in the trie

return current;

$\}$

Please use the pseduocode to help my code with the outlined tasks

Instructions #$2$

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

Instruction $3$ : Further, we can not use 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?