Tree
Trie (Prefix Tree)
[Medium] No.208 Implement Trie (Prefix Tree)
[Medium] 211. Add and Search Word - Data structure design
Trie node structure:
Insertion of a key in a trie:
![](images/208_TrieInsert.png)
(The above image is from leetcode.com.)
Time Complexity: O(N), where N is the key length.
Space Complexity: O(N), the worst case is to insert every single letter of key.
Search for a key in a trie:
![](images/208_TrieSearchKey.png)
(The above image is from leetcode.com.)
Time Complexity: O(N), where N is the number of nodes in the given list.
Space Complexity: O(1)
Search for a key prefix in a trie:
![](images/208_TrieSearchPrefix.png)
(The above image is from leetcode.com.)
Time Complexity: O(N), where N is the number of nodes in the given list.
Space Complexity: O(1)