Runtime: 45 ms + O(S) + C++ solution
Approach\nLets say,\n> words = ["a","banana","app","appl","ap","apply","apple"]\n\n Traverse through the words array and insert every word in Trie.\n Traverse a
## Approach\nLets say,\n> **words** = ["a","banana","app","appl","ap","apply","apple"]\n\n* Traverse through the words array and insert every word in `Trie`.\n* Traverse again and check whether `words[i]` contains all the prefixes or not.\n\n![ss-01](https://user-images.githubusercontent.com/32735407/168482696-55e7bfec-748b-4ca7-81d3-c7bab035d3d3.png)\n\nHere, we can see that `apple` and `apply` both are having all prefixes. So, both can be valid answers. But we need **lexicographically** the smallest one. So, the result is `apple`.\n\n## Complexity\n> **Time**: `O(S)` where, S = sum of all strings.\n> **Space**: `O(S)`\n\n## Code\n```cpp\nstruct TrieNode {\n    bool isWord = false;\n    TrieNode* children[26];\n    \n    bool containsKey(char key) {\n        return (children[key - \'a\'] != NULL);\n    }\n    \n    void put(char ch, TrieNode* node) {\n        children[ch - \'a\'] = node;\n    }\n    \n    TrieNode* nextNode(char ch) {\n        return children[ch - \'a\'];\n    }\n    \n    void setWord() {\n        isWord = true;\n    }\n};\n\nclass Trie {\nprivate: \n    TrieNode* root;\npublic: \n    Trie() {\n        root = new TrieNode();\n    }\n    \n    void insert(string word) {\n        TrieNode* curr = root;\n        for(auto &ch : word) {\n            if(!curr->containsKey(ch)) {\n                curr->put(ch, new TrieNode());\n            }\n            curr = curr->nextNode(ch);\n        }\n        curr->setWord();\n    }\n    \n    bool doesPrefixExist(string word) {\n        bool isExist = true;\n        TrieNode* curr = root;\n        for(auto &ch : word) {\n            if(curr->containsKey(ch)) {\n                curr = curr->nextNode(ch);\n                isExist = isExist & curr->isWord;\n            } else {\n                return false;\n            }\n        }\n        return isExist;\n    }\n};\n\nclass Solution {\npublic:\n    string longestWord(vector<string>& words) {\n        Trie trie;\n        string longest = "";\n        \n        for(auto &word : words) {\n            trie.insert(word);\n        }\n        \n        for(auto &word : words) {\n            if(trie.doesPrefixExist(word)) {\n                if(word.size() > longest.size()) {\n                    longest = word;\n                } else if(word.size() == longest.size() && word < longest) {\n                    longest = word;\n                }\n            }\n        }\n        \n        return longest;\n    }\n};\n```
['Trie', 'C']