Prefix tree
 Building a well balanced BST needs time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
 Using trie, search in O(M) time.
 The penalty is on trie storage requirements.
Implementation
 Every node of trie consists of multiple branches.
 Each branch represents a possible character of keys.
Mark the last node of every key as leaf node.
struct trie_node { int value; / Used to mark leaf nodes / trie_node_t *children[ALPHABET_SIZE]; };
Note that a nonterminating node can also be marked as leaf. Eg.
root
/ \ \
t 'a' b
  
h n 'y'
  \ \
'e' s 'y' 'e'
/  
i r w
/  
'r' 'e' e

'r'
The leaf nodes are quoted in ‘’.
Insert and search costs O(key_length), however the memory requirements of trie is O(ALPHABET_SIZE * key_length * N) where N is number of keys in trie.
Compressed trie, ternary search tree, etc. can be used to minimize memory requirements of trie.