Lazy Functional Inorder Binary Tree Traversal in Clojure
After a thorough google search for combinations of the terms "inorder", "in-order", "lazy", "tree", "traversal" and "Clojure", I still have not found an implementation of an inorder traversal of a binary tree in Clojure that returns a lazy sequence of nodes in order and does not throw a
StackOverflowError for very large or infinite binary trees. So let us add our own lazy, functional, inorder binary tree traversal in Clojure and hope that mentioning these terms so often helps Google to find it.
First we define a protocol that represents a binary tree without finalizing its concrete implementation. This will be especially helpful for traversing finite as well as infinite binary trees uniformly. We call the protocol
Node, since a binary tree consists of nodes that have left and right sub-nodes and the root node represents the whole binary tree:
A very simple representation of a binary tree can then be implemented with vectors:
But we can also implement an infinite tree. To visualize it, we only take the first 9 nodes of this infinite tree:
Here is the solution for a lazy, functional, inorder binary tree traversal in Clojure:
Given a binary tree, this implementation returns an inorder sequence of node values, which we can then map, filter and everything else we want to do with sequences in Clojure. It works even for the
infinite-tree from above:
To test whether this implementation is indeed lazy and does not throw a
StackOverflowError, we identify the 10.000th element of the inorder traversal sequence of a binary tree that is infinite on its right side:
Caveat: If we have a binary tree that is infinite on the left side of a node, we are out of luck: Because of the definition of inorder traversal, we have to follow each consecutive left sub-node before returning the value of a node and if there is always a left sub-node, we would follow this path forever, unable to return anything.
What other implementations are out there and what are their drawbacks?
The most prominent implementation is on Rosetta Code (I changed it only in the way that it makes use of the
Node protocol from above):
This function is intended to work with a callback, so we have to adapt it in a non-idiomatic way to make it return a sequence:
It is also not lazy and not suitable for a binary tree that is infinite on the right side:
I also found variations of this code:
This implementation does not work with callbacks but returns a sequence, which is what we usually want in Clojure. But it also throws a
StackOverflowError for large or infinite binary trees:
We developed an implementation of a lazy, functional, inorder binary tree traversal in Clojure, that is suitable for large and even some shapes of infinite binary trees. It does not depend on callbacks, but returns a lazy, inorder sequence of nodes. If one does not intend to change the underlying tree, the sequence abstraction is an idiomatic way to traverse a tree in Clojure.