Algorithm to Render a Horizontal Binary-ish Tree in Text/ASCII form
- by Justin L.
It's a pretty normal binary tree, except for the fact that one of the nodes may be empty.
I'd like to find a way to output it in a horizontal way (that is, the root node is on the left and expands to the right).
I've had some experience expanding trees vertically (root node at the top, expanding downwards), but I'm not sure where to start, in this case.
Preferably, it would follow these couple of rules:
If a node has only one child, it can be skipped as redundant (an "end node", with no children, is always displayed)
All nodes of the same depth must be aligned vertically; all nodes must be to the right of all less-deep nodes and to the left of all deeper nodes.
Nodes have a string representation which includes their depth.
Each "end node" has its own unique line; that is, the number of lines is the number of end nodes in the tree, and when an end node is on a line, there may be nothing else on that line after that end node.
As a consequence of the last rule, the root node should be in either the top left or the bottom left corner; top left is preferred.
For example, this is a valid tree, with six end nodes (node is represented by a name, and its depth):
[a0]------------[b3]------[c5]------[d8]
\ \ \----------[e9]
\ \----[f5]
\--[g1]--------[h4]------[i6]
\ \--------------------[j10]
\-[k3]
Which represents the horizontal, explicit binary tree:
0 a
/ \
1 g *
/ \ \
2 * * *
/ \ \
3 k * b
/ / \
4 h * *
/ \ \ \
5 * * f c
/ \ / \
6 * i * *
/ / \
7 * * *
/ / \
8 * * d
/ /
9 * e
/
10 j
(branches folded for compactness; * representing redundant, one-child nodes; note that *'s are actual nodes, storing one child each, just with names omitted here for presentation sake)
(also, to clarify, I'd like to generate the first, horizontal tree; not this vertical tree)
I say language-agnostic because I'm just looking for an algorithm; I say ruby because I'm eventually going to have to implement it in ruby anyway.
Assume that each Node data structure stores only its id, a left node, and a right node.
A master Tree class keeps tracks of all nodes and has adequate algorithms to find:
A node's nth ancestor
A node's nth descendant
The generation of a node
The lowest common ancestor of two given nodes
Anyone have any ideas of where I could start? Should I go for the recursive approach? Iterative?
