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 min-corner
"Returns a vector of the minimum non-empty row and column in sparse-string."
[sparse-string]
(mapv #(apply min (map % (keys sparse-string)))
[first second]))
(defn max-corner
"Returns a vector of one plus the maximum non-empty row and column in
sparse-string."
[sparse-string]
(mapv #(apply max (map % sparse-string))
[(comp inc first key) end-col]))
(defn fill
"Returns a string of newlines and spaces to fill the gap between entries x and
y in a sparse string whose minimum corner is corner."
[corner x y]
(let [[_ min-col] corner
[[prev-row _] _] x
[[next-row next-col] _] y]
(apply str (concat (repeat (- next-row prev-row) \newline)
(repeat (- next-col
(if (== prev-row next-row)
(end-col x)
min-col))
\space)))))
(defn sparse-str
"Converts sparse-string to a string."
[sparse-string]
(let [corner (min-corner sparse-string)]
(->> sparse-string
(sort-by key)
(cons [corner ""])
(partition 2 1)
(map (fn [[x y]] (str (fill corner x y) (val y))))
(apply str))))
(defn shift
"Creates and returns a sparse string by adding offset to the position of each
entry in sparse-string."
[offset sparse-string]
(into {} (map (fn [[pos s]]
[(mapv + pos offset) s])
sparse-string)))
(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 (- (second (max-corner left))
(second (min-corner right)))
2))
1))
(def directions {:left - :right +})
(defn diagonal
"Returns a diagonal sparse string with the top end located at corner."
[direction corner length character]
(let [[first-row first-col] corner]
(into {} (map (fn [n]
[[(+ first-row n)
((directions direction) first-col n)]
(str character)])
(range length)))))
(defn leg
"Returns a sparse string from shifting tree-string according to direction,
vert-gap, and value-height, merged with a diagonal strut."
[direction tree-string vert-gap value-height]
(merge (shift [(+ value-height vert-gap)
((directions direction) (inc vert-gap))]
tree-string)
(diagonal direction
[value-height ((directions direction) 1)]
vert-gap
({:left \/ :right \\} direction))))
(defn assemble
"Assembles a complete tree string from the tree strings of a value, left
subtree, and right subtree."
[value left right]
(if (or left right)
(let [[value-height _] (max-corner value)
vert-gap (vert-gap left right)]
(merge value
(when left
(leg :left left vert-gap value-height))
(when right
(leg :right right vert-gap value-height))))
value))
(defn tree-string
"Creates and returns a tree string from node."
[node]
(let [{:keys [value left right]} node
s (str value)]
(apply assemble
{[0 (- (quot (count s) 2))] s}
(map #(when % (tree-string %))
[left right]))))
Implementation notes
When printing a sparse string string, one first needs to find the minimum occupied row and column in the sparse string. This naturally leads to the end-col, min-corner, and max-corner functions for calculating bounding boxes for sparse strings.
Now, how does one print a sparse string? This problem basically boils down to printing the whitespace to fill the gaps between sparse string entries. Once that's accomplished, the actual sparse-str implementation is quite straightforward.
Also, since I'm going to be combining sparse strings in addition to just creating and printing them, I'll need a function to shift the reference point of an existing sparse string.
All we need now is a way to convert from that logical representation of the tree to the textual one, which is the task of the tree-string function.
As you can see, the better part of the work is done in that assemble function. The first thing we need to do is decide how long we're going to make the struts that connect the left and right subtrees. To simplify things, we'll just always make them the same length, which means that the length of the struts, calculated by vert-gap, will equal to the final distance between the bottom of the value tree string and the tops of the left and right tree strings.
And of course, we'll need the diagonal function to create the struts themselves.
Now that we have all the rest of the pieces, it's just a matter of assembleing them together. The leg function is just a helper that combines diagonal and shift together into something that can then be merged with the root.
Example
In case you'd like to test this code yourself, here's a function for generating a random binary tree:
(defn rand-tree
[weight depth]
(into {:value (int (Math/pow 2 (rand (dec Integer/SIZE))))}
(map #(when (and (pos? depth) (< (rand) weight))
[% (rand-tree weight (dec depth))])
[:left :right])))
So this...
(println (sparse-str (tree-string (rand-tree 3/4 3))))
... will print something like this:
1369616891
/ \
/ \
/ \
/ \
/ \
238883 2
/ \ /
/ \ 9
/ \ / \
/ \ 1 2222
2949729 6
/ /
1836 5299294
