Do you know the trees used in Cassandra, Git, Bitcoin or Lucene? Check this post to find interesting trees, usually not covered on Computer Science lectures.

Pretty standard tree. Pretty standard tree.

There are many types of trees which are covered on Computer Science lectures. Those usually include: Binary Search Tree, AVL Tree, B Tree, Splay Tree, Red-Black Tree, Trie Trees, Heap Trees.

Those are indeed very useful and practical trees with lots of applications. However, I’ve discovered few other trees while brushing up my knowledge about algorithms and data structures. Here they are, the most interesting, yet not so popular trees:

  • BK-Tree - do you want to find misspellings of a word in a dictionary? E.g. given word “dog” and dictionary { “cat”, “fog”, “dot”, “cookie” }, naive approach is to compare the word “dog” to all of the entries in the dictionary. This leads to O(n) time. It can be solved in O(lg n) time, though. Burkhard-Keller tree is used in Apache Lucene, for example. Head to Xenopax’s Blog for awesome post about BK-Trees.
  • Merkle Tree - probably you didn’t know but that’s the name of the tree of commits and blobs in a Git VCS. Another applications known to me personally include: Cassandra (during node repair) and Bitcoin blockchain.
  • Interval Tree - interesting idea of augmenting “normal” (single value) trees with additional data in order to solve windowing queries.
  • Lemon Tree - the most complicated type of tree. Many wondered what it really is, but few actually knew… Find the official statement here.