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.

Setup

{:deps {org.clojure/clojure {:mvn/version "1.10.1"}

        ;; complient is used for autocompletion

        ;; add your libs here (and restart the runtime to pick up changes)

        compliment/compliment {:mvn/version "0.3.9"}

        cc.artifice/vijual {:mvn/version "0.2.5"}}}

(require '[vijual])

(defn draw [tree]

  (vijual/draw-binary-tree tree)

  tree)

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:

(defprotocol Node

  (value [this])

  (left [this])

  (right [this]))

A very simple representation of a binary tree can then be implemented with vectors:

(extend-type clojure.lang.Indexed

  Node

  (value [node] (get node 0))

  (left [node] (get node 1))

  (right [node] (get node 2)))

(def b-tree [1 [2 [4 [7]] [5]] [3 [6 [8] [9]]]])

(draw b-tree)

But we can also implement an infinite tree. To visualize it, we only take the first 9 nodes of this infinite tree:

(defn take-tree

  ([counter tree] (take-tree (int (/ counter 2)) tree (class tree)))

  ([counter tree cls]

   (if (not (neg? counter))

     (recur (dec counter)

            (clojure.walk/postwalk

              (fn [x]

                (if (instance? cls x)

                  [(value x) (left x) (right x)]

                  x))

              tree)

            cls)

     (clojure.walk/postwalk

       (fn [x]

         (cond (instance? cls x) nil

               (and (vector? x) (some nil? x)) [(first x)]

               :else x))

       tree))))

(deftype RightInfinityNode [num]

  Node

  (value [_] num)

  (left [_] (when (even? num) (new RightInfinityNode (dec num))))

  (right [_] (when (even? num) (new RightInfinityNode (+ num 2)))))

(def infinite-tree (->RightInfinityNode 0))

(draw (take-tree 9 infinite-tree))

TL;DR Solution

Here is the solution for a lazy, functional, inorder binary tree traversal in Clojure:

(def take-some (take-while some?))

(defn in-order-seq

  ([root] (in-order-seq root ()))

  ([node stack]

   (when (or node (seq stack))

     (let [stack* (into stack take-some (iterate left node))

           node* (peek stack*)]

       (lazy-seq (cons (value node*)

                   (in-order-seq (right node*) (pop stack*))))))))

(in-order-seq b-tree)

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:

(take 9 (in-order-seq infinite-tree))

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:

(nth (in-order-seq infinite-tree) 1E4)

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):

(defn walk [node f order]

  (when node

    (doseq [o order]

      (if (= o :visit)

        (f (value node))

        (walk (o node) f order)))))

(defn inorder [node f]

  (walk node f [left :visit right]))

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:

(defn rc-inorder [node]

  (let [store (volatile! [])

        callback (fn [node] (vswap! store conj node))]

    (inorder node callback)

    @store))

(rc-inorder b-tree)

It is also not lazy and not suitable for a binary tree that is infinite on the right side:

(try (nth (rc-inorder infinite-tree) 1E4)

  (catch StackOverflowError e (prn e)))

I also found variations of this code:

(defn is-empty? [tree] (= tree nil))

(defn list-inorder [tree]

  (cond

      (is-empty? tree) ()

      :else (concat (list-inorder (left tree))

                    (list (value tree))

                    (list-inorder (right tree)))))

(list-inorder b-tree)

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:

(try (nth (list-inorder infinite-tree) 1E4)

  (catch StackOverflowError e (prn e)))

Conclusion

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.