figure standard trie for the strings {bearbellbidbullbuysellstockstopof string of in factfor each character that can follow the prefix [ kin string of the set sthere is child of labeled with character in this waya trie concisely stores the common prefixes that exist among set of strings as special caseif there are only two characters in the alphabetthen the trie is essentially binary treewith some internal nodes possibly having only one child (that isit may be an improper binary treein generalalthough it is possible that an internal node has up to |schildrenin practice the average degree of such nodes is likely to be much smaller for examplethe trie shown in figure has several internal nodes with only one child on larger data setsthe average degree of nodes is likely to get smaller at greater depths of the treebecause there may be fewer strings sharing the common prefixand thus fewer continuations of that pattern furthermorein many languagesthere will be character combinations that are unlikely to naturally occur the following proposition provides some important structural properties of standard trieproposition standard trie storing collection of strings of total length from an alphabet has the following propertiesthe height of is equal to the length of the longest string in every internal node of has at most |schildren has leaves the number of nodes of is at most the worst case for the number of nodes of trie occurs when no two strings share common nonempty prefixthat isexcept for the rootall internal nodes have one child