--- a/bk-tree.c++
+++ b/bk-tree.c++
@@ -10,6 +10,8 @@
 struct bk_tree
 {
   std::string word;
+  //For caching levenshtein distances
+  std::map<std::string, size_t> lev_cache;
   std::map<size_t, bk_tree*> children;
 };
 typedef std::map<size_t, bk_tree*> branches;
@@ -101,7 +103,12 @@
 bool query_tree( bk_tree & tree, std::string& word, size_t m)
 {
   size_t d;
-  if( (d = levenshtein(tree.word,word)) <= m)
+  if( tree.lev_cache.find(word) != tree.lev_cache.end())
+    d = tree.lev_cache[word];
+  else
+    tree.lev_cache[word] = d = levenshtein(tree.word,word);
+
+  if( d <= m)
     return true;
 
   bool found = false;