How to draw a tree with an arbitrary number of children?

I'm struggling with coming up with an algorithm which allows me to draw a tree like data structure where each node can have 0..n children. The issue for me is, I don't know how far apart I have to place nodes so that children won't overlap.

In this example the "d"s are children of "b" and the "g"s are children of "e" and they overlap on the x-axis when I just spread children out evenly above its parent given the total width of the tree.

              g g g g g g g g   (9 nodes)
              \ \ \ \ | / / /
d d d d d d d d d     e         (10 nodes)
\ \ \ \ / / / / /     |
       b              c         (2 nodes)
           \      /
              a                 (1 node)

The nodes are not ordered in any way. So it's actually more like a graph which has to look like a tree.

Solution

In order to determine the spacing, I suggest an algorithm which consists of three main steps. We will use the language of graph theory: The tree to be draw consists of nodes a, b, c, ...

Step 1. We start with determining the layer for each node which measures the distance to the root node a. We assume that you have prepared your tree as adjacency list which mainly a table with 2 columns, start-node and end-node of each edge. In the given example, we have a - b, a - c, b - d1, ... b - d9, c - e, e - g1, ...e - g9. Note the node naming scheme, which explicitly resolves the multiplicity of d and g. We end up with a table like this:

# node: layer
a: 0
b: 1
c: 1
d1: 2
d2: 2
...
d9: 2
e: 2
g1: 3
g2: 3
...
g9: 3

Step 2. We also have to determine and track the overall number of nodes per layer as well as the number of leaf nodes per layer, i.e. nodes without any sucessor. Leaves can be identified easily in the adjacency list as node-identifiers which occur only in the 2nd column, but not in the 1st column. In the given example, layer 0 and 1 are free of leaves, layer 2 has 9 leaves, namely d1 ... d9, and layer 3 has only leaves e1 ... e9. At this stage, we have constructed the following table:

# layer: leave nodes, overall nodes, non-leave nodes (in this layer)
0: 0, 1, 1
1: 0, 2, 2
2: 9, 10, 1
3: 9, 0, 0

Step 3. Finally, we expand the table which we just created with a column cumulative leaf count. All we do is to sum up how many leaf nodes we already encountered:

# layer: cumulative nodes
0: 0
1: 0
2: 9
3: 18

The result is 18, which is the number of columns needed to display the tree overlap-free.