Binary Trees are optimal except when they’re not
A binary search tree with string keys is just a compressed version of a binary tree with bit keys, which greatly reduces the number of nodes.<p>E.g. this has three nodes:<p><pre><code>    dog
   &#x2F;   \
  ant   fly
</code></pre>
But:<p><pre><code>  ant -&gt; 61 6E 74 -&gt; 011000010110111001110100
  dog -&gt; 64 6f 67 -&gt; 011001000110111101100111
  fly -&gt; 66 6C 79 -&gt; 011001100110110001111001
</code></pre>
Thus<p><pre><code>                              R
                             &#x2F;
                            0
                             \
                              1
                               \
                                1
                               &#x2F;
                              0
                             &#x2F;
                            0
                           &#x2F; \
                      ,---&#x27;   `-------.
                     &#x2F;                 \
                    &#x2F;                   \
                   0                     1
                  &#x2F;                     &#x2F; \
                 &#x2F;             ,-------&#x27;   `---.
                &#x2F;             &#x2F;                 \
               0             0                   1
                \           &#x2F;                   &#x2F;
                 1         0                   0
                &#x2F;         &#x2F;                   &#x2F;
               0         0                   0
                \         \                   \
                 1         1                   1
                  \         \                   \
                   1         1                   1
                  &#x2F;         &#x2F;                   &#x2F;
                 0         0                   0
                  \         \                   \
                   1         1                   1
                    \         \                   \
                     1         1                   1
                      \         \                 &#x2F;
                       1         1               0
                      &#x2F;           \             &#x2F;
                     0             1           0
                    &#x2F;             &#x2F;           &#x2F;
                   0             0           0
                    \             \           \
                     1             1           1
                      \             \           \
                       1             1           1
                        \           &#x2F;             \
                         1         0               1
                        &#x2F;         &#x2F;                 \
                       0         0                   1
                        \         \                 &#x2F;
                         1         1               0
                        &#x2F;           \             &#x2F;
                       0             1           0
                      &#x2F;               \           \
                     0                 1           1
                   (ant)             (dog)       (fly)
</code></pre>
:)