Printing binary trees

After writing this answer, I was inspired to try to design a more elegant solution to the problem of printing binary trees. And what better tool with which to seek elegance than Clojure?

Overall design

The solution I ended up with involved creating, merging, and printing what I'm going to call sparse strings. A sparse string is simply a map from row/column pairs to substrings. These substrings must not contain newlines or overlap with each other.

So for instance, this multiline string

baz
     foo
bar
              qux

could be represented by this sparse string:

{[3 -2] "foo"
 [4 -7] "bar"
 [2 -6] "baz"
 [5 7] "qux"}

A few things to note:

• Empty space is simply filled by regular spaces and newlines

• The first coordinate is the row, the second coordinate is the column

• The first row and column need not necessarily be zero

The problem of printing a binary tree then reduces to creating sparse strings from its left and right subtrees (as well as one for its value, which will go at the top), then shifting and merging those sparse strings together.

The only extra requirement when using sparse strings to represent trees is that the root (or the center of the root, if the root is wider than 1 character) must be at [0 0]. Consider the tree below:

4
   / \
  2   5
 / \
1   3

The in-memory representation of this would be

{:value 4
 :left {:value 2
        :left {:value 1}
        :right {:value 3}}
 :right {:value 5}}

Textually, the tree would be represented as

{[0 0] "4"
 [2 -2] "2"
 [4 -4] "1"
 [3 -3] "/"
 [4 0] "1"
 [3 -1] "\\"
 [1 -1] "/"
 [2 2] "5"
 [1 1] "\\"}

I'll refer to this as a tree string. This way, when I combine multiple tree strings to create a bigger tree string, I can safely use [0 0] as an anchor point from which to shift subtrees.

Code

```
(defn end-col
"Returns one plus the maximum column occupied by the sparse string entry x."
[x]
(let [[[_ col] s] x]
(+ col (count s))))

(defn m

First of all, in my opinion, both the algorithm is nice and interesting, and the code is really well-written, broken down into easily understandable functions!
Well done!

The only addition that I can make are corner-cases (and their possible fixes) for some of the helper functions. However, please note, that from the main entry point, I did not find any way to trigger these corner cases, so, from a user perspective, the program works well even without the changes below.

Corner case # 1

(min-corner {})
(sparse-str {})

Both throw an exception, due to min in min-corner being called with zero arguments.

I suggest the following change, in order to handle this case:

(defn min-corner
   "Returns a vector of the minimum non-empty row and column in sparse-string."
   [sparse-string]
   (mapv #(apply min (let [args (map % (keys sparse-string))] (if (empty? args) [0 0] args)))
;  (mapv #(apply min (map % (keys sparse-string)))
         [first second]))

I.e., call min with a default value (in this case [0 0]), if the arguments are empty.

Corner case #2

(max-corner {})

Similar issue, like for min-corner, similar solution:

(defn max-corner 
   "Returns a vector of one plus the maximum non-empty row and column in
   sparse-string."
   [sparse-string]
   (mapv #(apply max (let [args (map % sparse-string)] (if (empty? args) [0 0] args)))
;  (mapv #(apply max (map % sparse-string))
         [(comp inc first key) end-col]))

Corner case #3

(sparse-str {[0 0] "aa" [0 1] "b"})

This will return aab. However, b is misplaced here, because it should be at position [0 1], and it is, instead, at position [0 2].
To be honest, I don't really know what would be the best solution here. I can imagine the following:

• Leave it as it is: all output is shown, some of it might be on the wrong place.

• Overwrite the the end of the first string with the second one (i.e. "ab").

• Overwrite the beginning of the second string with the first one (in this case: "aa").

• Throw an exception.

Again, starting from the main entry point, it is not possible to trigger this situation, because the user does not provide any positions. However, in case the helper functions were to be reused in a library, this is a question that should be addressed.

Corner case #4

(vert-gap {[0 0] "a"} {[4 10] "a"})

In case the right element has a bigger second coordinate than the left one, the result is always 1. I'm not sure if this is by design, but if not, then I'd suggest to make sure, that vertical gap is calculated correctly also in such cases, by taking the absolute value of the difference, instead of the difference itself:

(defn vert-gap
   "Returns the minimum vertical gap that can be used in combining the left and
   right tree strings."
   [left right]
   (if (and left right)
     (max 1 (quot (Math/abs (- (second (max-corner left))
                     (second (min-corner right)))
                  ) 2))
   1))

Corner case # 5

(diagonal :left [0 0] -2 \a)

With the current implementation, this will return an empty result: {}. Now, with the semantics that the name of the parameter length implies, this should be correct (maybe an exception could be thrown, but that is only detail).
However, wouldn't it be nice, if the signum of length could control the direction, in which the first coordinate grows? Something like this:

(defn diagonal
   "Returns a diagonal sparse string with the top end located at corner."
   [direction corner length character]
   (let [[first-row first-col] corner
         _length (Math/abs length)
         op (if (< length 0) - +)]
     (into {} (map (fn [n]
                     [[(op first-row n)
                       ((directions direction) first-col n)]
                      (str character)])
                   (range _length)))))

In this way, the result of the above example will be: {[0 0] "a", [-1 -1] "a"}.
Of course, it might be worth considering to rename the length parameter, e.g. to horizontal-displacement or something similar.

P.S.:

I setup a github repo for the above mentioned changes, and their corresponding test cases (along other tests):

StackExchange Code Review Q#120369, answer score: 17