# 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"}}}`
deps.edn
Extensible Data Notation

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]))`
0.1s
Clojure

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 ] ] [3 [6  ]]])`
`(draw b-tree)`
1.0s
Clojure

But we can also implement an infinite tree. To visualize it, we only take the first 9 nodes of this infinite 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))`
0.7s
Clojure

## 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)`
0.1s
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:

`(take 9 (in-order-seq infinite-tree))`
0.0s
Clojure

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)`
0.2s
Clojure

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]))`
0.1s
Clojure

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)`
0.0s
Clojure

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)))`
0.7s
Clojure

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)`
0.0s
Clojure

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)))`
0.5s
Clojure

## 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.