Trie Interview Questions and Answers

Trie (also called **digital tree **or prefix tree) is a
tree-based data structure, which is used for efficient
retrieval

of a key in a large data-set of strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated; i.e., the value of the key is distributed across the structure. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Each complete English word has an arbitrary integer value associated with it (see image).

Some applications of trie data structure include: dictionary lookup prefix searches auto complete feature in text editors command completion in IDE etc phone number/contacts searching IP lookups mapping URLs to operations on a web server matching sentences (if a trie based on a sequence of words, like Gmail autocompletion)

index a complete text (as the Ukkonen suffix tree algorithm alternative)

Advantages of Trie: With Trie, we can insert and find strings in O(L) time where L represent the length of a single word. A BST performs O(log n) comparisons of keys, where n is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takes O(m log n) time. Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function (also, the order of hash collisions is implementation defined), which is usually meaningless. Tries facilitate longest-prefix matching, helping to find the key sharing the longest possible prefix of characters all unique. By avoiding the hash function, tries are generally faster than hash tables for small keys like integers and pointers. With Trie there is no need to compute any hash function and no collision handling is required. Tries require less space in comparison to BST. Because the keys are not stored explicitly, only an amortised constant amount of space is needed to store each key. Deletion is straightforward Disadvantages of Trie: The main disadvantage of tries is that they need a lot of memory for storing strings. In the worst case, there is one node per character. All those little node allocations start adding up. Imagine a dictionary that contains 200,000 words, and the average word length is five characters. That's a million nodes of overhead. A well constructed hash table (i.e. a good hash function and a reasonable load factor) has O(1) lookup time. Lookup time in a trie is O(m) : it depends on the length of the string you're looking up.

The basic form is that of a linked set of nodes, where each node contains an array of child pointers, one for each symbol in the alphabet (so for the English alphabet, one would store 26 child pointers and for the alphabet of bytes, 256 pointers). This is simple but wasteful in terms of memory (as the structure wastes space storing null pointers).

// trie node
class TrieNode {
  public TrieNode[] children = new TrieNode[ALPHABET_SIZE];
  // isEndOfWord is true if the node represents
  // end of a word
  public bool isEndOfWord;
  public TrieNode() {
    isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++)
    children[i] = null;
  }
};

An alternative implementation represents a node as a triple (symbol, child, next) and links the children of a

node together as a singly linked list: child points to the node's first child, next to the parent node's next child:

function Trie(parent, prev, key, value) {
  if (key !== void 0)
  this.key = key;
  // single-character key
  if (value !== void 0)
  this.value = value;
  // user-defined value
  if (prev)
  prev.next = this;
  // next sibling node
  else if (parent)
  parent.child = this;
  // first child node
}
Another alternative in order to avoid the use of an array of 256 pointers (ASCII), is to store the alphabet array

as a bitmap of 256 bits representing the ASCII alphabet, reducing dramatically the size of the nodes.

Tries and hash tables are used for different things: If all you want is the ability to lookup a word, then a hash table will be faster. A well constructed hash table (i.e. a good hash function and a reasonable load factor) has O(1) lookup time. If you want to find common prefixes, ordered retrieval, or do similar things, then you want a trie. Lookup time in a trie is O(m) : it depends on the length of the string you're looking up. And memory wise: A hash table's overhead is typically a constant multiple of the number of words it contains. That is, in addition to the memory required to store the strings, there is per-string overhead to store the mapping between hash code and string. Memory for a trie is a little more involved. In the worst case, there is one node per character. All those little node allocations start adding up. Imagine a dictionary that contains 200,000 words, and the average word length is five characters. That's a million nodes of overhead.

The following are the main advantages of tries over hash tables: Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function (also, the order of hash collisions is implementation defined), which is usually meaningless. Tries facilitate longest-prefix matching, but hashing does not, as a consequence of the above. Performing such a "closest fit" find can, depending on implementation, be as quick as an exact find.

Tries tend to be faster on average at insertion than hash tables because hash tables must rebuild their index when it becomes full - a very expensive operation. Tries therefore have much better bounded worst case time costs, which is important for latency sensitive programs. By avoiding the hash function, tries are generally faster than hash tables for small keys like integers and pointers.

The following are the main advantages of tries over binary search trees (BSTs): Looking up keys is faster. Looking up a key of length m takes worst case O(m) time. A BST performs O(log n) comparisons of keys, where n is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takes O(m log n) time. Moreover, in the worst case log(n) will approach m . Also, the simple operations tries use during lookup, such as array indexing using a character, are fast on real machines. Tries are more space efficient when they contain a large number of short keys, because nodes are shared between keys with common initial subsequences. Tries facilitate longest-prefix matching, helping to find the key sharing the longest possible prefix of characters all unique. The number of internal nodes from root to leaf equals the length of the key. Balancing the tree is therefore no concern.

A hash table can look up individual strings very quickly. It's like a thoroughbred racehorse. That's all it can do. A trie, on the other hand, is a workhorse that can do a lot of things. It'll never be as fast at lookups as a hash table, but it can do lots of things that the hash table can't do. For example, finding all the words in a hash table that start with "pre" will take O(n) time because you have to search all of the words. With a trie, it takes three probes to find the subtree that contains all of those words, and then all you have to do is traverse that subtree. Sure, the worst case is O(n) , but that's only if all the words in your trie start with "pre".