![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/BitwiseTreesScaling.png/220px-BitwiseTreesScaling.png)
In computer science, a trie, also called digital tree or sometimes radix tree or prefix tree (because we can search by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually 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. 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. Values are normally not ...