SVG Tree printer

Simple tree drawing logic generating SVG image using D3 library.

Algorithm

We use extremally simple recoursive function to print the tree. It walks and prints the tree in postorder traversal mode and it's complexity is O(n).

This way we first print the children so then we know where to print the parent (exactly in the middle of them).

Printing order:

              12
       ┍------+-----┑
       6            11
    ┍--+--┑      ┍--+--┑
    1     5      7     10
       ┍--|--┑      ┍--+--┑
       2  3  4      8     9

Steps:

1. If it has children draw them first
   • pass current x and incremented depth to the recursive call
   • set the value of x based on returned result (shifted x if children were printed)
2. Draw the node
   • set final coordinates based on passed x and current depth
   • draw node box
   • draw connection lines to all the children (as they were drawn already)
   • return container max x value (edge of descendants container + space)
3. Return new x value - the minimal value where the next node can be drawn. It has to be the end of the most right descendant incremented by the space (which we want to have between the nodes)

Listing

function drawSubTree(node: Node, x: number, depth: number, container: d3.Selection<"g">) {
    for (const child of node.children) {
        x = drawSubTree(child, x, depth + 1, container);
    }

    return node.drawAndGetRightEdge(container, x, depth);
}

Result