I had an interview last week and one of the early questions was about how to implement a search-as-you-type field. To be honest, I didn’t come up with the answer I should have - a tree where each character the user types represents the next node on the way toward the leaves.

I’ve been frustrated for the last several days at missing something that I really think I shouldn’t have missed… so I put together some code to do it (and a small wrapper app).

BSMatchTree takes strings, and then lets you retrieve those strings by either starting to type the string, or by any word within that string. The sample app I wrapped around the tree is pretty inefficient - it sets up and takes down the tree repeatedly. But that can easily be fixed. Also, the code only handles strings right now, but it could easily be updated to handle more complex structures with string keys or string components.

Here’s the code.

Here’s a sample app.