Challenge: Find All of the Words in a Trie

If you are given a Trie, can you return every word it contains in sorted order? A solution is placed in the "solution" section to help you, but we would suggest you try to solve it on your own first.

Problem Statement

In this problem, you have to implement the findWords() function to return all of the words stored in the Trie in alphabetically sorted order.

Function Prototype:

ArrayList<String> findWords(TrieNode root);

Here, root is the root node of Trie.

Output:

In the form of an ArrayList, it returns all of the words stored in the Trie in lexicographic order.

Sample Input

String keys[] = {"the", "a", "there", "answer", "any",
                     "by", "bye", "their","abc"};

Sample Output

"a", "abc","answer","any","by","bye","the","their","there"

Explanation

There are 9 words total in the given keys array, so we just need to iterate the Trie and return all of the words present in it.

Here’s an illustration of the given challenge:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.